【LeetCode】9 单词拆分②

题目

140. 单词拆分 II

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明:

  • 分隔时可以重复使用字典中的单词。

  • 你可以假设字典中没有重复的单词。

示例 1:

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]
示例 2:

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3:
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

方法 1:暴力

算法

解决此题最简单的方法是使用回溯。为了找到解,我们检查字符串(ss)的所有可能前缀是否在字典中,如果在(比方说 s1s1 ),那么调用回溯函数并检查剩余部分的字符串。
如果剩余部分可以形成有效拆分,这个函数返回前缀 s1s1 ,并将回溯调用的剩余结果(即 s-s1s−s1)跟在 s1s1 的后面。否则,返回空列表。

package com.janeroad;


import java.util.*;

public class test3 {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        return word_Break(s, wordDict, 0);
    }
    public List<String> word_Break(String s, Set<String> wordDict, int start) {
        LinkedList<String> res = new LinkedList<>();
        if (start == s.length()) {
            res.add("");
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end))) {
                List<String> list = word_Break(s, wordDict, end);
                for (String l : list) {
                    res.add(s.substring(start, end) + (l.equals("") ? "" : " ") + l);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Set<String> testSet = new HashSet<String>();
        testSet.add("cat");
        testSet.add("cats");
        testSet.add("and");
        testSet.add("sand");
        testSet.add("dog");
        test3 test3=new test3();
        System.out.println(test3.wordBreak("catsanddog",testSet));
    }
}

image.png

方法 2:记忆化回溯

算法

在之前的方法中,我们可以看出许多子问题的求解都是冗余的,也就是我们对于相同的子串调用了函数多次。

为了避免这种情况,我们使用记忆化的方法,我们使用一个 key:valuekey:value 这样的哈希表来进行优化。在哈希表中, keykey 是当前考虑字符串的开始下标, valuevalue 包含了所有从头开始的所有可行句子。下次我们遇到相同位置开始的调用时,我们可以直接从哈希表里返回结果,而不需要重新计算结果。

通过记忆化的方法,许多冗余的子问题都可以被省去,回溯树得到了剪枝,所以极大程度降低了时间复杂度。

public class Solution {

    public List<String> wordBreak(String s, Set<String> wordDict) {
        return word_Break(s, wordDict, 0);
    }
    HashMap<Integer, List<String>> map = new HashMap<>();

    public List<String> word_Break(String s, Set<String> wordDict, int start) {
        if (map.containsKey(start)) {
            return map.get(start);
        }
        LinkedList<String> res = new LinkedList<>();
        if (start == s.length()) {
            res.add("");
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end))) {
                List<String> list = word_Break(s, wordDict, end);
                for (String l : list) {
                    res.add(s.substring(start, end) + (l.equals("") ? "" : " ") + l);
                }
            }
        }
        map.put(start, res);
        return res;
    }
}

image.png

方法 3:使用动态规划

算法
image.png

public class Solution {
   public List<String> wordBreak(String s, Set<String> wordDict) {
       LinkedList<String>[] dp = new LinkedList[s.length() + 1];
       LinkedList<String> initial = new LinkedList<>();
       initial.add("");
       dp[0] = initial;
       for (int i = 1; i <= s.length(); i++) {
           LinkedList<String> list = new LinkedList<>();
           for (int j = 0; j < i; j++) {
               if (dp[j].size() > 0 && wordDict.contains(s.substring(j, i))) {
                   for (String l : dp[j]) {
                       list.add(l + (l.equals("") ? "" : " ") + s.substring(j, i));
                   }
               }
           }
           dp[i] = list;
       }
       return dp[s.length()];
   }
}

image.png

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×