题目

image.png

代码

  1.     //1.暴力递归
  2.     public boolean wordBreak(String s, List<String> wordDict) {
  3.         return recur(s, s.length());
  4.     }
  6.     public boolean recur(String s, int index) {
  7.         if (index == 0) return true;
  8.         for (int i = index - 1; i >= 0; i--) {
  9.             if (recur(s, i) && wordDict.contains(s.substring(i, index)))
  10.                 return true;
  11.         }
  12.         return false;
  13.     }
  15.     //2.备忘录
  16.     int[] dp;
  17.     public boolean wordBreak(String s, List<String> wordDict) {
  18.         dp = new int[s.length()];
  19.         return recur(s, s.length());
  20.     }
  22.     public boolean recur(String s, int index) {
  23.         if (index == 0) return true;
  24.         for (int i = index - 1; i >= 0; i--) {
  25.             if (dp[i] != 0) {
  26.                 if (dp[i] == -1) continue;
  27.                 if (dp[i] == 1 && set.contains(s.substring(i, index))) return true;
  28.             }
  29.             boolean res = recur(s, i);
  30.             dp[i] = res == true ? 1 : -1;
  31.             if (res && wordDict.contains(s.substring(i, index)))
  32.                 return true;
  33.         }
  34.         return false;
  35.     }
  37.     //3.动态规划
  38.     public boolean wordBreak(String s, List<String> wordDict) {
  39.         boolean[] dp = new boolean[s.length() + 1];
  40.         dp[0] = true;
  41.         for (int i = 1; i <= s.length(); i++) {
  42.             for (int j = i; j <= s.length(); j++) {
  43.                 dp[j] |= wordDict.contains(s.substring(i - 1, j)) && dp[i - 1];
  44.                 if (dp[s.length()]) return true;
  45.             }
  46.         }
  47.         return false;
  48.     }
  50.     //如果求组合数就是外层for循环遍历物品，内层for遍历背包。
  51.     //如果求排列数就是外层for遍历背包，内层for循环遍历物品。
  52.     //4.完全背包方面
  53.     public boolean wordBreak(String s, List<String> wordDict) {
  54.         boolean[] dp = new boolean[s.length() + 1];
  55.         dp[0] = true;
  56.         for (int i = 1; i <= s.length(); i++) { //遍历背包
  57.             for (int j = 0; j < i; j++) { //遍历物品
  58.                 if (dp[j] && wordDict.contains(s.substring(j, i))) {
  59.                     dp[i] = true;
  60.                     break;
  61.                 }
  62.             }
  63.         }
  64.         return dp[s.length()];
  65.     }

单词拆分