LeetCode-139-单词拆分

139. 单词拆分

难度中等1020收藏分享切换为英文接收动态反馈

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

根据前缀划分

image-20210616093630719

class Solution {
    public static boolean wordBreak(String s, List<String> wordDict) {
        return process(s, 0, new HashSet<>(wordDict)) != 0;
    }

    // s[0......index-1]这一段，已经分解过了，不用在操心
    // s[index.....] 这一段字符串，能够被分解的方法数，返回
    public static int process(String s, int index, HashSet<String> wordDict) {
        if (index == s.length()) {
            return 1;//是一种有效的划分
        }
        int ways = 0;
        for (int end = index; end < s.length(); end++) {
            // s[index....end]
            String pre = s.substring(index, end + 1);
            if (wordDict.contains(pre)) {
                ways += process(s, end + 1, wordDict);
            }
        }
        return ways;
    }
}

image-20210616094348795

动态规划

public static int process(String s, int index, HashSet<String> wordDict) 递归过程，一个可变参数index ，改DP

class Solution {
   public static boolean wordBreak(String s, List<String> wordDict) {
   HashSet<String> set = new HashSet<>(wordDict);
   int N = s.length();
   int[] dp = new int[N + 1];
   // dp[i] = process(s, i, set)的返回值
   dp[N] = 1;
   for (int index = N - 1; index >= 0; index--) {
      int ways = 0;
      for (int end = index; end < s.length(); end++) {
         // s[index....end]
         String pre = s.substring(index, end + 1);
         if (set.contains(pre)) {
            ways += dp[end + 1];
         }
      }
      dp[index] = ways;
   }
   return dp[0] != 0;
}
}

image-20210616095253917

动态规划+前缀树剪枝

class Solution {
   public static class Node {
        public boolean end;
        public Node[] nexts;

        public Node() {
            end = false;
            nexts = new Node[26];
        }
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        Node root = new Node();
        for (String str : wordDict) {
            char[] chs = str.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.end = true;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            Node cur = root;
            for (int end = i; end < N; end++) {
                cur = cur.nexts[str[end] - 'a'];
                if (cur == null) {
                    break;
                }
                if (cur.end) {
                    dp[i] += dp[end + 1];
                }
            }
        }
        return dp[0] != 0;
    }
}

image-20210616100920189