Java DP solution


  • 7
    public class Solution {
        
      public List<String> wordBreak(String s, Set<String> dict) {
        List<String> res = new ArrayList<String>();
        // Do a fast check and see if we can break the input string
        if (!canBreak(s, dict))
          return res;
        
        helper(s, dict, 0, "", res);
        return res;
      }
      
      void helper(String s, Set<String> dict, int start, String sol, List<String> res) {
        if (start == s.length()) {
          res.add(sol);
          return;
        }
        
        for (int i = start; i < s.length(); i++) {
          String sub = s.substring(start, i + 1);
          
          if (dict.contains(sub))
            helper(s, dict, i + 1, sol + (sol.length() == 0 ? "" : " ") + sub, res);
        }
      }
      
      // Solution from "Word Break"
      boolean canBreak(String s, Set<String> dict) {
          if (s == null || s.length() == 0) return false;
          
          int n = s.length();
          
          // dp[i] represents whether s[0...i] can be formed by dict
          boolean[] dp = new boolean[n];
          
          for (int i = 0; i < n; i++) {
              for (int j = 0; j <= i; j++) {
                  String sub = s.substring(j, i + 1);
                  
                  if (dict.contains(sub) && (j == 0 || dp[j - 1])) {
                      dp[i] = true;
                      break;
                  }
              }
          }
          
          return dp[n - 1];
      }
    
    }

  • 0
    H

    just backtracking


  • 0
    A

    Even though the code is a bit longer. But to me, this version is a classical style to solve many permutation problem.


  • 0
    X

    Time exceed limit


  • 0
    D

    Time exceed limit


  • 0
    J

    it's not DP, here is my DP version

    
        public List<String> wordBreak(String s, List<String> wordDict) {
            HashSet<String> set = new HashSet<>(wordDict);
            if (s.length() == 0 || !canBreak(s, set)) return new ArrayList<>();
            char[] chars = s.toCharArray();
            List<String>[] dp = new List[chars.length];
    
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < chars.length; i++) {
                dp[i] = new ArrayList<>();
                sb.setLength(0);
                for (int j = i; j >= 0; j--) {
                    sb.insert(0, chars[j]);
                    String word = sb.toString();
                    if(set.contains(word)) {
                        if (j == 0) {
                            dp[i].add(word);
                        } else {
                            for (String prev : dp[j - 1]) {
                                dp[i].add(prev + " " + word);
                            }
                        }
                    }
                }
            }
            return dp[chars.length - 1];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.