leetcode 139. 单词拆分 解题思路

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解题思路

这个题还是有一点难度的，需要明确的是，字典中是存在前缀词的，比如“aaa”,"aaaa"可以同时存在于字典中，所以基本排除了On的可能性。

第一种思路是利用递归，方法是按从左到右顺序遍历字符串，将当前第i个字符，与之前的字符拼接成单词，在字典中查找，如果字典中存在该单词，那么继续递归遍历s从i到结尾的子字符串，同时还要考虑第i个字符并不是单词结尾的可能，继续向后遍历。一直到整个字符串s的尾部，如果刚好有个单词的结尾在s的尾部，那么结束遍历。
语言的描述有点抽象，但是代码写起来是很简洁的。

代码实现如下:

    public static boolean wordBreakHist(String s, List<String> wordDict) {
        char[] arr = s.toCharArray();
        String curWord = "";
        for (int i = 0; i < arr.length; i++) {
            curWord += arr[i];
            if (wordDict.contains(curWord)) {
                if (i == arr.length - 1) {
                    return true;
                }
                if (wordBreak(s.substring(i + 1), wordDict)) {
                    return true;
                }
            }
        }
        return false;
    }

但是迭代效率太低，跑到这个用例的时候报超时了。

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

继续优化一下思路，考虑用动态规划来做。
首先我们知道，当s可以被拆分的时候，s必然是由一个单词结尾的。也就说s是否可拆分，可以简化为，能否找到一个位置i，使得s(0,i)为一个可拆分的字符串，而s(i+1,leng)为一个单词。
即 dp[length] = max{dp[i] * s(i,leng)}； 其中dp[i]=1表示s(0,i)为一个可拆分的字符串，s(i,leng)=1表示s(i+1,leng)为一个单词。
根据这个思路，我们对s进行遍历，显然由于每次dp[i]的变化都会影响后续dp的计算，所以我们需要On2的遍历次数。或者说，我们需要对s字符串中，每一个可以组成字符串的子串进行计算，所以需要On2的遍历，代码中s(j,i)即代表每种可能的结尾单词。
另外，我们需要计算一下dp的初值，显然当s为一个单词时，dp[s]=1
即 dp[s] = dp[0] * s(0,leng);
由此我们可以求得dp[0]=1。

以下是代码实现：

    public static boolean wordBreak(String s, List<String> wordDict) {
        char[] arr = s.toCharArray();
        boolean[] dp = new boolean[arr.length + 1];
        dp[0] = true;
        for (int i = 0; i <= arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[arr.length];

    }

两种方法比较，使用动态规划确实要比迭代快很多。

image.png

另附测试代码：

    public static void main(String[] args) {
        List<String> wordDict = new ArrayList<>();
        wordDict.add("aaaa");
        wordDict.add("aaa");
        System.out.println(wordBreak("aaaaaaa", wordDict));
        List<String> wordDict2 = new ArrayList<>();
        String test = "";
        for (int i = 0; i < 10; i++) {
            test += "a";
            String test2 = test;
            wordDict2.add(test2);
        }
        long start = System.currentTimeMillis();
        System.out.println(wordBreak(
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
                wordDict2));
        long end = System.currentTimeMillis();
        System.out.println("wordBreak cost "+(end-start));
        start=end;
        System.out.println(wordBreakHist(
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
                wordDict2));
        end = System.currentTimeMillis();
        System.out.println("wordBreakHist cost "+(end-start));

    }