本文共 1640 字，大约阅读时间需要 5 分钟。

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]Output: trueExplanation: Return true because "leetcode" can be segmented as "leet code"

分析：注意超时问题

1. 动态规划问题，R[I]=R[0,J] && R[J,I] &&R[I,END]. 

public boolean wordBreak(String s, List
   
     wordDict) {        boolean[] match = new boolean[s.length()+1];//注意长度比s大1，因为substring是左闭右开        match[0] = true;//默认第一个是true才能开始循环        for(int i=1;i<=s.length();i++){            for(int j=0;j
   

2. 递归 利用string 的startswith 方法

/**     * 搜索字符串是否可以被分割成单词串     *     * @param s       字符串     * @param idx     处理的开始位置     * @param wordMap 单词字典，开始字符相同的在同一个set集合中     * @return 搜索结果     */    public boolean wordBreak(String s, int idx, Map
   
    > wordMap) {        if (idx >= s.length()) {            return true;        }        Set
    
      words = wordMap.get(s.charAt(idx));        if (words != null) {            for (String word : words) {                // idx之前的字符已经匹配，如果从ide之后起匹配word单词                if (s.startsWith(word, idx)) {                    // 递归处理                    boolean result = wordBreak(s, idx + word.length(), wordMap);                    // 如果满足条件，返回true                    if (result) {                        return true;                    }                }            }        }        return false;    }
    
   

参考

转载地址：http://infni.baihongyu.com/