Share my simple 4ms Java DP Solution beating 88.74%


  • 0

    The idea is simple, use DP and check from tail to front. If there is a match, continue search.

    public class Solution {
        int[] dp;
        Set<String> set;
        public boolean wordBreak(String s, Set<String> wordDict) {
            dp = new int[s.length()];
            set = wordDict;
            return helper(s, s.length()-1);
        }
        public boolean helper(String s, int start){
            if(start<0) return true;
            if(dp[start]==1) return true;
            if(dp[start]==-1) return false;
            boolean ret = false;
            for(String str : set){
                int j = str.length()-1;
                int k = start;
                while(j>=0 && k>=0 && str.charAt(j) == s.charAt(k)){
                    j--;
                    k--;
                }
                if(j==-1) ret = ret || helper(s, k);
            }
            if(ret==true) dp[start] = 1;
            else dp[start] = -1;
            return ret;
        }
    }
    

Log in to reply
 

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