【Leetcode】139.拆分词句

d2aebbb8-ca5a-4d2f-9c4c-889a1b9fac83_0.jpg

题目

给定一个非空字符串 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

思路分析

暴力搜索

这道题最开始我们想的肯定是每个字符遍历, 然后去看是不是在wordDict里面。而wordDict是一个list,查找是o(N)的时间复杂度,需要把这个时间复杂度先降下来,用Set把每次查找的时间复杂度降到o(1)。

怎么去check一个字符串wordDict能不能被组成,一个很朴素的想法就是把每个字符串分作两段,然后递归。比如如下代码。

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return helper(s, new HashSet<>(wordDict), 0);
    }
    public boolean helper(String s, Set<String> wordDict, int start) {
        if (start == s.length()) {
            return true;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) 
                && helper(s, wordDict, end)) {
                return true;
            }
        }
        return false;
    }
}

很显然这种思路是行不通的,因为时间复杂度太高,有兴趣的同学可以试一下。

  • 时间复杂度: O(n^n)
  • 空间复杂度:O(n)

记忆化搜索

重复计算太多。哪里重复了?举个例子:

输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
for 循环中:
首次递归: s = 'A' + helper('AAleetcodeB'), 最终检查不符合;
二次递归: s = 'AA' + helper('AleetcodeB'), 最终检查不符合;
三次递归: s = 'AAA' + helper('leetcodeB'), 最终检查不符合;

发现没, 上面每一次都重复计算了helper('leetcodeB')

节省时间的办法也很自然:要是我们能把搜索过的内容记下来就好了。记忆有两种办法可供参考:

  • 动态规划
  • 记忆化数组进行搜索

动态规划

我们先看动态规划,动态规划其实很好理解,最重要的是状态转移方程。不懂的同学,可以手动模拟一遍基本就理解了。

  • dp[i]表示[0, i] 子串是否能够由wordDict组成
  • dp[i] = 对于任意j, dp[j] && wordDict 包含 s[j + 1, i],其中j 属于区间 [0, i] 。

模拟一下动态规划的过程是:

输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
dp[0] = true // 初始化.
首次dp: dp[1] = true, wordDict 包含'A';
二次dp: dp[2] = true, 
        dp[1] = true, wordDict 包含'A';
三次dp: dp[3] = true,
        dp[1] = true, wordDict 包含'AA';
...
最后一次dp: dp[12] = false,
        dp[1]= true wordDict 不包含'AAleetcodeB';
        dp[2]= true wordDict 不包含'AleetcodeB';
        dp[3]= true wordDict 不包含'leetcodeB';
        dp[7]= true wordDict 不包含'codeB';
        dp[11]= true wordDict 不包含'B'
        故,dp[12] = false.

java版本代码如下:

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null) return false;
        Set<String> wordSet = new HashSet<>();
        for (int i = 0; i < wordDict.size(); i++) {
            wordSet.add(wordDict.get(i));
        }
        boolean[] dp = new boolean[s.length() + 1];
        // 状态开始
        dp[0] = true;
        // dp[i]表示能不能到达第i个字母的时候
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                String current = s.substring(j, i);
                if (dp[j] && wordSet.contains(current)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
  • 时间复杂度:O(n^2)。两层for循环。
  • 空间复杂度: O(n)。dp数组长度是n。

DFS

动态规划和记忆化搜索都是很常用的解法,本题我们可以用一个数组memoToEndContain 记下位置i到字符串结束能不能够由wordDict组成。还是我们最开始的例子:

输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
首次for循环: 'A' 可以被 wordDict组成
        'AA' 可以被 wordDict组成
        ...
        'AAAleetcodeB'不可以被 wordDict组成
        这次深搜后记住:
        从第一个字母'A' 第二个字母'A', 第三个字母'A' ... 开始的子串都不能由wordDict组成;

java代码:

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null) return false;
        Set<String> wordSet = new HashSet<>(wordDict);
        // 记忆从i到字符串结束能不能搜索到.
        Boolean[] memoToEndContain = new Boolean[s.length()];
        return dfs(s, 0, wordSet, memoToEndContain);
    }

    public boolean dfs(String s,
                       int start,
                       Set<String> wordSet,
                       Boolean[] memoToEndContain) {
        // 搜索到最后.
        if (start == s.length()) {
            return true;
        }
        // 之前已经搜索过.
        if (memoToEndContain[start] != null) {
            return memoToEndContain[start];
        }

        for (int end = start + 1; end <= s.length(); end++) {
            if (wordSet.contains(s.substring(start, end)) 
                && dfs(s, end, wordSet, memoToEndContain)) {
                return memoToEndContain[start] = true;
            }
        }
        memoToEndContain[start] = false;
        return memoToEndContain[start];
    }
}
  • 时间复杂度:O(n^2)。搜索树的大小最多达到 n^2 。
  • 空间复杂度: O(n)。深度优先二叉搜索树深度最多是n。
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,214评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,307评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,543评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,221评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,224评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,007评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,313评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,956评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,441评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,925评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,018评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,685评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,234评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,240评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,464评论 1 261
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,467评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,762评论 2 345

推荐阅读更多精彩内容