Oh, no! You have just completed  a lengthy  document when you have an  unfortu-nate Find/Replace mishap.  You have accidentally  removed all spaces, punctuation,and  capitalization  in  the document. A sentence like  "I reset  the  computer.  It  stilldidn't boot!" would become "iresetthecomputeritstilldidntboot".  You figure that youcan add back in the punctation and capitalization later, once you get the individualWords PRoperly separated. Most of the words will be in a dictionary,  but some strings,like proper names, will  not.Given a dictionary  (a list of words), design an algorithm  to find the optimal way of"unconcatenating" a sequence of words. In this case, "optimal" is defined  to be theparsing  which  minimizes  the number  of unrecognized sequences of characters.For example, the string "jesslookedjustliketimherbrother"  would be optimally parsedas  "JESS looked just like TIM her brother". This parsing  has seven unrecognized  char-acters, which  we have capitalized  for  clarity.

這是CareerCup Chapter 17的第14題，我沒怎么看CareerCup上的解法，但感覺這道題跟Word Break, Palindrome Partition II很像，都是有一個dictionary, 可以用一維DP來做，用一個int[] res = new int[len+1];res[i] refers to minimized # of unrecognized chars in first i chars, res[0]=0, res[len]即為所求。

有了維護量，現在需要考慮轉移方程，如下：

int unrecogNum = dict.contains(s.substring(j, i))? 0 : i-j; //看index從j到i-1的substring在不在dictionary里，如果不在，unrecogNum=j到i-1的char數res[i] = Math.min(res[i], res[j]+unrecogNum);

親測，我使用的case都過了，只是不知道有沒有不過的Corner Case:

 1 package fib; 2  3 import java.util.Arrays; 4 import java.util.HashSet; 5 import java.util.Set; 6  7 public class unconcatenating { 8     public int optway(String s, Set<String> dict) { 9         if (s==null || s.length()==0) return 0;10         int len = s.length();11         if (dict.isEmpty()) return len;12         int[] res = new int[len+1]; // res[i] refers to minimized # of unrecognized chars in first i chars13         Arrays.fill(res, Integer.MAX_VALUE);14         res[0] = 0;15         for (int i=1; i<=len; i++) {16             for (int j=0; j<i; j++) {17                 String str = s.substring(j, i);18                 int unrecogNum = dict.contains(str)? 0 : i-j;19                 res[i] = Math.min(res[i], res[j]+unrecogNum);20             }21         }22         return res[len];23     }24 25 26     public static void main(String[] args) {27         unconcatenating example = new unconcatenating();28         Set<String> dict = new HashSet<String>();29         dict.add("reset");30         dict.add("the");31         dict.add("computer");32         dict.add("it");33         dict.add("still");34         dict.add("didnt");35         dict.add("boot");36         int result = example.optway("johnresetthecomputeritdamnstilldidntboot", dict);37         System.out.print("opt # of unrecognized chars is ");38         System.out.println(result);39     }40 41 }

output是：opt # of unrecognized chars is 8