Leetcode日记–139.word break

发布于 2020-11-01  109 次阅读


碎碎念:SN真的可惜,前三把打得都很好,只是下路实在是太突破口了。。

题目:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
  Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

思路:

这个题目因为需要一个词一个词地比较,为了不重复比较,我们需要存储之前的结果,这就说明这题需要使用Dynamic Programming 来实现。

dp解决的问题我们需要找到递推公式。

我们设dp[i]为布尔类型,其意义为:位置i前面的字符可以按照要求被分词。

对于dp[i] , 我们需要依次遍历其前面的i-1个位置, 我们这里设遍历到的位置为j(0<j<i).当j前面的字符可以按照要求被词典分词,且j到i位置上的子字符串等于字典的某个词。则可以认为dp[i]为true。

再考虑具体实现,若想要判断子字符串是否在字典中,必然是使用hash结构的contains方法快速判断。因此我们把字典值存储在hashSet中。

同时也可以做一些简单的剪枝,枚举分割点的时候倒着枚举,如果分割点 jj 到 ii 的长度已经大于字典列表里最长的单词的长度,那么就结束枚举,但是需要注意的是下面的代码给出的是不带剪枝的写法。

代码:

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet<String>(wordDict);
        boolean [] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i=1;i<dp.length;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&wordDictSet.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[dp.length-1];
    }
}

你好哇!欢迎来到雷公马碎碎念的地方:)