原文链接:

给定一个字符串s和一个单词字典，确定是否可以将s分割为一个或多个字典单词的空格分隔的序列。

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

因为"leetcode"可以分割为"leet code", 所以返回true.

1. 普通方法
   这个问题可以用一种简单的方法来解决。讨论总是可以从这个开始。

public class Solution {    public boolean wordBreak(String s, Set
     
       dict) {             return wordBreakHelper(s, dict, 0);    }     public boolean wordBreakHelper(String s, Set
      
        dict, int start){        if(start == s.length())             return true;         for(String a: dict){            int len = a.length();            int end = start+len;             //end index should be <= string length            if(end > s.length())                 continue;             if(s.substring(start, start+len).equals(a))                if(wordBreakHelper(s, dict, start+len))                    return true;        }         return false;    }}
      
     

时间是O(n ^ 2)和超过了时间限制。

1. 动态程序
   利用动态规划方法解决这个问题的关键是:

定义一个数组t[]，这样t[i]= =true => 0-(i- 1)可以使用字典进行分段初始状态t[0]= = true

public class Solution {    public boolean wordBreak(String s, Set
     
       dict) {        boolean[] t = new boolean[s.length()+1];        t[0] = true; //set first to be true, why?        //Because we need initial state         for(int i=0; i
      
        s.length())                    continue;                 if(t[end]) continue;                 if(s.substring(i, end).equals(a)){                    t[end] = true;                }            }        }         return t[s.length()];    }}
      
     

时间:O(字符串长度*字典大小)。

1. Java解决方案3 -简单高效
   在方案2中, 如果字典的数据量是非常大的, 时间是非常长的.相反,我们可以解决这个问题在O(n ^ 2)时间(n是字符串的长度).

public boolean wordBreak(String s, Set
     
       wordDict) {    int[] pos = new int[s.length()+1];     Arrays.fill(pos, -1);     pos[0]=0;     for(int i=0; i