Java dp solution without using substring, O(N^2)


  • 0
    W
    public class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            //base case
            if(s == null || s.length() == 0) return false;
            //use dp and scan from right to left to avoid using substring
            boolean[] M = new boolean[s.length() + 1];
            M[s.length()] = true;
            for(int i = s.length() - 1; i >= 0; --i) {
                StringBuilder sb = new StringBuilder();
                for(int j = i; j < s.length(); ++j) {
                    sb.append(s.charAt(j));
                    //remember convert stringbuilder to string
                    if(wordDict.contains(sb.toString()) && M[j + 1]) {
                        M[i] = true;
                        break;
                    }
                }
            }
            return M[0];
        }
    }
    

Log in to reply
 

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