/*
Given a string and dictionary of words, break the string into minimum number of words from the dictionary.
Ex:
{"jumped", "over", "some", "thing”, "something"}
"jumpedoversomething",
0000010002000300003
Should return { “jumped”, “over”, “something”}
*/
fb: 求最少几次 直接return can[length]
class Solution {
public static void main(String[] args) {
HashSet<String> set = new HashSet<String>();
set.add("jumped");
set.add("over");
set.add("some");
set.add("thing");
set.add("something");
String target = "jumpedoversomething";
List<String> res =wordBreak(target, set);
for (String ss : res) {
System.out.println(ss);
}
}
public static List<String> wordBreak(String s, HashSet<String> wordDict) {
int[] can = new int[s.length() + 1];
HashMap<Integer, Integer> map = new HashMap<>();
int max = maxWordLength(wordDict);
// function
can[0] = 1;
for(int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= max && j <= i; j++) {
if (can[i - j] == 0) {
continue;
}
String sub = s.substring(i - j, i);
if (wordDict.contains(sub)) {
if (can[i] == 0) {
can[i] = can[i - j] + 1;
map.put(i, i - j);
} else if (can[i - j] + 1 < can[i]) {
can[i] = can[i - j] + 1;
map.put(i, i - j);
}
}
}
}
List<String> ans = new ArrayList<>();
int i = s.length(), j = 0;
for (int k = 0; k < can[s.length()] - 1; k++) {
j = (int) map.get(i);
ans.add(s.substring(j, i));
i = j;
}
return ans;
}
private static int maxWordLength(Set<String> wordDict) {
int max = 0;
for (String word: wordDict) {
max = Math.max(max, word.length());
}
return max;
}
}