SRM302

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

---

Division One - Level Three:

Solution

Use Dynamic Programming. I was intentionally to use Trie to solve this problem, but I didn't find the hole to solve it. The detail is showed in the comment of code.

Source Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: antonio081014
 * 
 *          SRM302_DIV1_900.java
 * 
 * 
 */
public class JoinedString {

    private List<String> words;

    public void unique() {
 while (true) {
     boolean flag = false;
     for (int i = 0; i < words.size(); i++) {
  for (int j = 0; j < words.size(); j++) {
      if (i != j && words.get(i).contains(words.get(j))) {
   flag = true;
   words.remove(j);
   break;
      }
  }
  if (flag)
      break;
     }
     if (!flag)
  break;
 }
    }

    public String joinWords(String[] _words) {
 words = new ArrayList<String>(Arrays.asList(_words));
 unique();
 int N = words.size();
 // for (int i = 0; i < N; i++)
 // System.out.println(words.get(i));

 // append[i][j] is the string shared between string i and j, here the
 // string starts with j, ends with i;
 String[][] append = new String[N][N];
 // mask[i][j] is the mask for appended string which shows the which
 // string is the substring of the appended string.
 int[][] mask = new int[N][N];

 for (int i = 0; i < N; i++)
     for (int j = 0; j < N; j++)
  append[i][j] = "";

 for (int i = 0; i < N; i++)
     for (int j = 0; j < N; j++) {
  if (i != j) {
      int minlen = Math.min(words.get(i).length(), words.get(j)
       .length());
      while (minlen > 0) {
   if (words.get(j).endsWith(
    words.get(i).substring(0, minlen)))
       break;
   else
       minlen--;
      }
      // This is the shared part, which could be empty if there is
      // no common part.
      append[i][j] = words.get(j).substring(0,
       words.get(j).length() - minlen);
      // This is the combined string;
      String str = append[i][j] + words.get(i);
      for (int k = 0; k < N; k++)
   if (str.contains(words.get(k)))
       mask[i][j] |= 1 << k;
  }
     }

 // With the mask, shows the combined string which starts with string i;
 // The mask shows which string is the substring of this string;
 String[][] f = new String[1 << N][N];
 for (int i = 0; i < 1 << N; i++)
     for (int j = 0; j < N; j++)
  f[i][j] = "";
 // Initialization, each only has itself.
 for (int i = 0; i < N; i++)
     f[1 << i][i] = words.get(i);

 for (int i = 0; i < 1 << N; i++) {
     for (int j = 0; j < N; j++) {
  // it has a start;
  if (f[i][j].length() > 0) {
      for (int k = 0; k < N; k++) {
   // if mask i does not have all the string which combined
   // string of j, k has.
   if (k != j && (i | mask[j][k]) > i) {
       int newMask = i | mask[j][k];
       String str = append[j][k] + f[i][j];
       if (cmp(str, f[newMask][k]))
    f[newMask][k] = str;
   }
      }
  }
     }
 }

 String ret = "";
 for (int i = 0; i < N; i++)
     // for each combined string, which has all the string as substring,
     // so mask has to be 11...1; string starts with ith string. we need
     // the smallest one;
     if (f[(1 << N) - 1][i].length() > 0 && cmp(f[(1 << N) - 1][i], ret))
  ret = f[(1 << N) - 1][i];

 return ret;
    }

    public boolean cmp(String a, String b) {
 if (b.length() == 0)
     return true;
 if (a.length() < b.length())
     return true;
 if (a.length() == b.length() && a.compareTo(b) < 0)
     return true;
 return false;
    }

}

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

Solution

Source Code:

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

Source Code:

---

Division Two - Level One:

Solution

Source Code: