[Leetcode] Word Break 单词分解

Ververica 发布于2019-08-14 12:24 / 1262人阅读

摘要：所以只要验证满足这个条件，我们则可以确定这个较长的字符串也是可分解的。同时，我们用数组记录下字符串长度递增时可分解的情况，以供之后使用，避免重复计算。当遍历完这个词典并找出所有以第一个字母开头的词以后，我们进入下一轮搜索。

Word Break I

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

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

Return true because "leetcode" can be segmented as "leet code".

动态规划 复杂度

时间 O(N^2) 空间 O(N)

思路

如果一个单词存在一种分解方法，分解后每一块都在字典中，那必定满足这么一个条件：对于该单词的最后一个分割点，这个分割点到单词末尾所组成的字符串是一个单词，而这个分割点到单词开头所组成的字符串也是可分解的。所以只要验证满足这个条件，我们则可以确定这个较长的字符串也是可分解的。

finishleetcode
finishleetco de
true         false
finishleet code
false      true
finish leetcode
true   true

所以我们用外层循环来控制待验证的字符串的长度，而用内层的循环来寻找这么一个分割点，可以把字符串分成一个单词和一个同样可分解的子字符串。同时，我们用数组记录下字符串长度递增时可分解的情况，以供之后使用，避免重复计算。

代码

public class Solution {
    public boolean wordBreak(String s, Set wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        Arrays.fill(dp,false);
        dp[s.length()]=true;
        // 外层循环递增长度
        for(int i = s.length()-1; i >=0 ; i--){
            // 内层循环寻找分割点
            for(int j = i; j < s.length(); j++){
                String sub = s.substring(i,j+1);
                if(wordDict.contains(sub) && dp[j+1]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
}

Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

动态规划 复杂度

时间 O(N^2) 空间 O(N^2)

思路

我们从第一个字母开始，遍历字典，看从第一个字母开始能组成哪个在字典里的词，如果找到一个，就在这个词的结束位置下一个字母处，建立一个列表，记录下这个词（保存到一个列表的数组）。当遍历完这个词典并找出所有以第一个字母开头的词以后，我们进入下一轮搜索。下一轮搜索只在之前找到的词的后面位置开始，如果这个位置不是一个词的下一个字母位置，我们就跳过。这样我们相当于构建了一个树（实际上是列表数组），每个找到的词都是这个树的一个分支。有了这个“树”，然后我们再用深度优先搜索，把路径加到结果当中就行了。

c
a
t                *              *
s -- cat         |              |
a -- cats        cats          cats
n                             /
d                            /
d -- and, sand      and    sand
o                          /
g                         /
  -- dog                dog

注意

在backtracking的时候不用考虑下标超界（小于0）的情况，直接将所有到0的都加入结果就行了，因为我们在建这个路径时，就是从0开始建的，不可能超界。

代码

public class Solution {
    
    public List res = new LinkedList();
    
    public List wordBreak(String s, Set wordDict) {
        List dp[] = new ArrayList[s.length()+1];
        dp[0] = new ArrayList();
        for(int i = 0; i < s.length(); i++){
            // 只在单词的后一个字母开始寻找，否则跳过
            if(dp[i]==null) continue;
            // 看从当前字母开始能组成哪个在字典里的词
            for(String word : wordDict){
                int len = word.length();
                if(i + len > s.length()) continue;
                String sub = s.substring(i, i+len);
                if(word.equals(sub)){
                    if(dp[i + len] == null){
                        dp[i + len] = new ArrayList();
                    }
                    dp[i + len].add(word);
                }
            }
        }
        // 如果数组末尾不存在单词，说明找不到分解方法
        if(dp[s.length()]!=null) backTrack(dp, s.length(), new ArrayList());
        return res;
    }
    
    private void backTrack(List dp[], int end, ArrayList tmp){
        if(end <= 0){
            String path = tmp.get(tmp.size()-1);
            for(int i = tmp.size() - 2; i >= 0; i--){
                path += " " + tmp.get(i);
            }
            res.add(path);
            return;
        }
        for(String word : dp[end]){
            tmp.add(word);
            backTrack(dp, end - word.length(), tmp);
            tmp.remove(tmp.size()-1);
        }
    }
}

云服务器 GPU云服务器 break-word word-break LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64457.html

leetcode140. Word Break II

摘要：题目要求现在有一个非空字符串和一个非空的字典。现在向中添加空格从而构成一个句子，其中这个句子的所有单词都存在与中。题目要求 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence ...

huayeluoliuhen 2019-08-15 14:29 评论0 收藏0
[Leetcode] Length of Last Word 最后一个单词长度

摘要：代码双指针法复杂度时间空间思路从后往前看字符串，跳过所有空格后，记下该结束位置，再到下一个空格，再记录一个开始位置，则长度就是结束位置减去开始位置。 Length of Last Word Given a string s consists of upper/lower-case alphabets and empty space characters , return the l...

happen 2019-08-14 12:46 评论0 收藏0
[Leetcode] Alien Dictionary 外文字典

摘要：拓扑排序复杂度时间空间思路首先简单介绍一下拓扑排序，这是一个能够找出有向无环图顺序的一个方法假设我们有条边，先将每个节点的计数器初始化为。最后，我们开始拓扑排序，从计数器为的字母开始广度优先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...

pkhope 2019-08-14 12:38 评论0 收藏0
Word Squares

摘要：题目链接暴力遍历，一个一个检查看符不符合要求。首先这种需要求出所有结果的题，一般都是用的。因为题目已经说了的长度范围是到，最多考虑五个单词即可。首先是肯定都需要的，两种或者。如果题目要求返回所有以特定的开头的单词，那么可以用。 Valid Word Square 题目链接：https://leetcode.com/problems... 暴力遍历，一个一个检查看符不符合要求。 ...

JerryZou 2019-08-14 17:19 评论0 收藏0
890-查找和替换模式

摘要：前言的的题目查找和替换模式，原题目描述如下你有一个单词列表和一个模式，你想知道中的哪些单词与模式匹配。如果存在字母的排列，使得将模式中的每个字母替换为之后，我们就得到了所需的单词，那么单词与模式是匹配的。前言 LeetCode的Weekly Contest 98的题目查找和替换模式，原题目描述如下：你有一个单词列表 words 和一个模式 pattern，你想知道 words 中...

haobowd 2019-08-19 10:59 评论0 收藏0