fork(1) download
copy 
  1. import java.util.*;
  2.  
  3. /**
  4.  * Created with IntelliJ IDEA.
  5.  * User: uerturk
  6.  * Date: 08/10/13
  7.  * Time: 17:04
  8.  * To change this template use File | Settings | File Templates.
  9.  */
  10. class HasChain {
  11.  
  12.     Map<Character, List<String>> startsWithStringMap = new HashMap<Character, List<String>>();
  13.     Map<Character, List<String>> endsWithStringMap = new HashMap<Character, List<String>>();
  14.  
  15.     private Character getFirstChar(String str) {
  16.         return str.charAt(0);
  17.     }
  18.  
  19.     private Character getLastChar(String str) {
  20.         return str.charAt(str.length() - 1);
  21.     }
  22.  
  23.     boolean hasChain(List<String> stringList) {
  24.         for (String str : stringList) {
  25.             Character start = getFirstChar(str);
  26.             Character end = getLastChar(str);
  27.             List<String> startsWithList;
  28.             List<String> endsWithList;
  29.  
  30.             if (startsWithStringMap.containsKey(start)) {
  31.                 startsWithList = startsWithStringMap.get(start);
  32.             } else {
  33.                 startsWithList = new ArrayList<String>();
  34.                 startsWithStringMap.put(start, startsWithList);
  35.             }
  36.  
  37.             if (endsWithStringMap.containsKey(end)) {
  38.                 endsWithList = endsWithStringMap.get(end);
  39.             } else {
  40.                 endsWithList = new ArrayList<String>();
  41.                 endsWithStringMap.put(end, endsWithList);
  42.             }
  43.             startsWithList.add(str);
  44.             endsWithList.add(str);
  45.         }
  46.  
  47.         Stack<String> stringStack = new Stack<String>();
  48.         for (String str : stringList) {
  49.             if (hasChain(stringList.size(), str, stringStack)) {
  50.                 System.out.println(stringStack);
  51.  
  52.                 return true;
  53.             }
  54.         }
  55.  
  56.         return false;
  57.     }
  58.  
  59.     private boolean hasChain(int size, String startString, Stack<String> stringStack) {
  60.         if (size == stringStack.size()) return true;
  61.         Character last = getLastChar(startString);
  62.         if (startsWithStringMap.containsKey(last)) {
  63.             List<String> stringList = startsWithStringMap.get(last);
  64.             for (int i = 0; i < stringList.size(); i++) {
  65.                 String candidate = stringList.remove(i--);
  66.                 stringStack.push(candidate);
  67.                 if (hasChain(size, candidate, stringStack)) {
  68.                     return true;
  69.                 }
  70.                 stringStack.pop();
  71.                 stringList.add(++i, candidate);
  72.             }
  73.         }
  74.  
  75.         return false;
  76.     }
  77.  
  78.     public static void main(String[] args) {
  79.         List<String> stringList = new ArrayList<String>();
  80.         stringList.add("bd");
  81.         stringList.add("fk");
  82.         stringList.add("ab");
  83.         stringList.add("kl");
  84.         stringList.add("cf");
  85.         stringList.add("ff");
  86.         stringList.add("fa");
  87.         stringList.add("ak");
  88.         stringList.add("ka");
  89.         stringList.add("lf");
  90.         stringList.add("bc");
  91.  
  92.         System.out.println(new HasChain().hasChain(stringList));
  93.  
  94.         stringList.remove("ka");
  95.  
  96.         System.out.println(new HasChain().hasChain(stringList));
  97.  
  98.     }
  99. }
  100.  
Success #stdin #stdout 0.08s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[bc, cf, fk, kl, lf, ff, fa, ak, ka, ab, bd]
true
false
https://ideone.com/cdbhQf
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!