Work break

這題我原本想用 string concatination 來做，但實在太多條件

後來看解說是要用 dp

概念是建立一個一維 boolean array，其值代表到 i 這個位置的字串是否可以用字典裡的字組合成

例如： s = penapple, dict = ["pen", "apple"], f[9] = true 表示 penapple 這個字可以用字典組合成，

f[3] = true 表示 pen 這個字可以用字典組合成

要注意的是我們把陣列宣告為字串長度+1，且 f[0] = true，用來處理 "" 的情況，而且之後的 substring 也比較好用

然後可以加速處理時間，因為 substring(i-j, i) 假如超過字典裡的最大長度也沒有判斷必要，因為不可能會組合得成

public boolean wordBreak(String s, Set<String> dict) {
    if (s == null) {
        return false;
    }

    int max = Integer.MIN_VALUE;
    for(String d: dict){
        max = d.length()>max?d.length():max;
    }

    boolean f[] = new boolean[s.length()+1];
    f[0] = true;
    for (int i=1; i<=s.length(); i++) {
        for (int j=1; j<=max && j<=i; j++) {
            String sub = s.substring(i-j, i);
            if (dict.contains(sub) && f[i-j]) {
                f[i] = true;
                break;
            }
        }
    }

    return f[s.length()];
}

point:

• dp 的想法
• 子字串長度比字典裡最大的還大則無需判斷