leetcode经典例题——单词拆分

单词拆分

题目描述：

 

   1、动态规划

思路：这道题是要我们单词拆分来，能用字符串列表这个数组组成，我们就可以用到动态规划：

初始化 dp=[false,……,false]，长度为 n+1。n 为字符串长度。dp[i] 表示 s 的前 i 位是否可以用 wordDict 中的单词表示。初始化 dp[0]=True，空字符可以被表示。

当我们遍历s单词字符串时，如果dp[i] =false,则退出循环，证明我们无法拼接到这个位置；

如果dp[i] = true,我们遍历字符串列表，依次匹配，看是否能匹配至s单词字符串，匹配成功，则设置该位置dp[word.length+1] = true;

看看代码：

public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len+1];
        dp[0] = true;
        for(int i = 0;i<len;i++){
            if(!dp[i]) continue;
            for(String word : wordDict){
                while ( s.startsWith(word,i)){
                    dp[word.length()+i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }

 时间复杂度：O(m*n)，m为单词s的长度，n为字典wordDict的数量

空间复杂度：O(n)

2、回溯算法

思路：这道题既然是依次拼接，也就是一道排列组合题，我们也可以用回溯算法来解决

回溯算法就也是利用遍历wordDict，判断s.startsWith(word,i)为true时进行递归，

如果该次递归成功，我们返回结果true；

如果该次递归不成功，我们回溯，仍旧遍历wordDict进行判断是否下一次递归，直到wordDict遍历完成，仍没结果才返回false；

进入代码：

public boolean wordBreak(String s, List<String> wordDict) {
    return backTrack(0,s,wordDict);
}
public boolean backTrack(int len,String s,List<String> wordDict){
    if (len == s.length()) return true;
    for (String word : wordDict) {
        if (s.startsWith(word,len)){
            if (backTrack(len+word.length(),s,wordDict))
                return true;
        }
    }
    return false;
}

注：该回溯算法有一个弊端，在leetcode运行时，由于它设置一个单词s为aaaaaaaaaaaaaa……wordDict["a","aa","aaa",……]，我们用回溯算法时，由于会优先进行第一个"a"的匹配，所以可能出现超时情况！

持续更新关于leetcode的文章中~