Given a string s and a dictionary of words dict, determine if s can be
segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73074

题解

单序列(DP_Sequence) DP 题,由单序列动态规划的四要素可大致写出:

  1. State: f[i] 表示前i个字符能否根据词典中的词被成功分词。
  2. Function: f[i] = or{f[j], j < i, letter in [j+1, i] can be found in dict}, 含义为小于i的索引j中只要有一个f[j]为真且j+1i中组成的字符能在词典中找到时,f[i]即为真,否则为假。具体实现可分为自顶向下或者自底向上。
  3. Initialization: f[0] = true, 数组长度为字符串长度 + 1,便于处理。
  4. Answer: f[s.length]

考虑到单词长度通常不会太长,故在s较长时使用自底向上效率更高。

public class Solution { 
    public boolean wordBreak(String s, List<String> wordDict) { 
        boolean[] result = new boolean[s.length() + 1]; 
        result[0] = true; 
         
        int maxWordLength = 0; 
        for (String word : wordDict) { 
            maxWordLength = maxWordLength > word.length() ? maxWordLength : word.length(); 
        } 
         
        for (int i = 1; i < s.length() + 1; i++) { 
            for (int j = i - 1; j >= 0; j--) { 
                if (i - j > maxWordLength) { 
                    result[i] = false; 
                    break; 
                } 
                String temp = s.substring(j, i); 
                if (result[j] && wordDict.contains(temp)) { 
                    result[i] = true; 
                    break; 
                } 
            } 
        } 
        return result[s.length()]; 
    } 
}.length()];
    }
}
Advertisements