力扣labuladong一刷day63天单词拆分

力扣labuladong一刷day63天单词拆分

一、139. 单词拆分

题目链接：https://leetcode.cn/problems/word-break/description/
思路：s是否能被拆分成字典中的单词，单词数量是不限的，故是完全背包问题，不限数量的单词是否能组成字符串s，可以看的出来，并不是要求你长度相等就可以，还得有一定的顺序才能排列成字符串s，故本题还是一个排列问题。for循环的遍历顺序，背包在外物品在内是排列，物品在外背包在内是组合。
定义dp[i]表示，s[0, i]可以被字典元素拼出来，那么如果s[j, i]是字典元素，且dp[j]是true，就说明dp[i]可以被拼出。
故递推公式为 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(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 && !dp[i]; j++) {
                if (set.contains(s.substring(j, i)) && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

另外采用回溯的方法也可以做，不过要把遍历改为子问题，下面这个就是改造成分解子问题，当前片段存在字典中，只要后续的都可以拼接说明字符串s可以被拼接。

if (set.contains(s.substring(index, i+1))) {
	 boolean subProblem = dp(s,i+1);
}

class Solution {
    Set<String> set;
    int[] visited;
    public boolean wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        visited = new int[s.length()];
        Arrays.fill(visited, -1);
        return dp(s, 0);
    }

    boolean dp(String s, int index) {
        if (index == s.length()) {
            return true;
        }
        if (visited[index] != -1) {
            return visited[index] != 0;
        }
        for (int i = index; i < s.length(); i++) {
            if (set.contains(s.substring(index, i+1))) {
                boolean subProblem = dp(s,i+1);
                if (subProblem) {
                    visited[i] = 1;
                    return true;
                }
            }
        }
        visited[index] = 0;
        return false;
    }
}

二、140. 单词拆分 II

题目链接：https://leetcode.cn/problems/word-break-ii/description/
思路：处理字符串的排列组合还是回溯更好处理一些，本题采用回溯的方法进行处理，很简单的回溯模板。

class Solution {
    LinkedList<String> track;
    List<String> res;
    List<String> wordDict;
    public List<String> wordBreak(String s, List<String> wordDict) {
        track = new LinkedList<>();
        res = new LinkedList<>();
        this.wordDict = wordDict;
        dp(s, 0);
        return res;
    }
    void dp(String s, int index) {
        if (index == s.length()) {
            res.add(String.join(" ", track));
            return;
        }
        for (String word : wordDict) {
            int len = word.length();
            if (index + len <= s.length() && s.substring(index, index + len).equals(word)) {
                track.addLast(word);
                dp(s, index+len);
                track.removeLast();
            }
        }
    }
}