Java DP solution


  • 28
    public boolean wordBreak(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
    F
    This post is deleted!

Log in to reply
 

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