@@ -0,0 +1,1526 @@
+import java.util.HashSet;%0A%0A// CTCI: 17.13%0A// CTCI only has brute force and memoization (right -%3E left) solutions. This solution is dynamic%0A// programming (left -%3E right), uses O(n) space and runs in O(n%5E2) time.%0A// To find actual splits (spaces) we maintain separate array with positions.%0A//%0A// Example:%0A// Respace.respace(Array(%22looked%22, %22just%22, %22like%22, %22her%22, %22brother%22), %22jesslookedjustliketimherbrother%22)%0A// res0: String = jess looked just like tim her brother%0A// Respace.respace(Array(%22reset%22, %22computer%22, %22it%22, %22did%22, %22not%22, %22boot%22), %22resetthecomputeritdidnotbootmike%22)%0A// res3: String = reset the computer it did not boot mike%0Apublic class Respace %7B%0A  public static String respace(String%5B%5D words, String text) %7B%0A    HashSet%3CString%3E dict = new HashSet%3CString%3E();%0A    for (String w : words) %7B%0A      dict.add(w);%0A    %7D%0A    int%5B%5D dp = new int%5Btext.length() + 1%5D; // contains unrecognized characters%0A    int%5B%5D ps = new int%5Btext.length() + 1%5D; // contains split positions%0A    for (int i = 1; i %3C= text.length(); i++) %7B%0A      dp%5Bi%5D = Integer.MAX_VALUE;%0A      ps%5Bi%5D = -1;%0A      for (int j = 0; j %3C i; j++) %7B%0A        String t = text.substring(j, i);%0A        int rnk = dp%5Bj%5D + (dict.contains(t) ? 0 : t.length());%0A        if (dp%5Bi%5D %3E rnk) %7B%0A          dp%5Bi%5D = rnk;%0A          ps%5Bi%5D = j;%0A        %7D%0A      %7D%0A    %7D%0A    StringBuilder sb = new StringBuilder();%0A    sb.append(text);%0A    for (int i = ps.length - 1; i %3E 0; i--) %7B%0A      if (ps%5Bi%5D != ps%5Bi - 1%5D) %7B%0A        sb.insert(ps%5Bi%5D, %22 %22);%0A      %7D%0A    %7D%0A    return sb.toString();%0A  %7D%0A%7D%0A

add solution