力扣labuladong一刷day63天单词拆分

文章目录

• • • 力扣labuladong一刷day63天单词拆分
    • 一、139. 单词拆分
    • 二、140. 单词拆分 II

      一、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 wordDict) {
              Set 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 set;
          int[] visited;
          public boolean wordBreak(String s, List 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 track;
          List res;
          List wordDict;
          public List wordBreak(String s, List 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();
                  }
              }
          }
      }
      

       
       建筑网招工网  网上平台怎么弄的  线上设计师招聘  建站公司高端定制  华为云建站模板  营销网站都有哪些