9 ms Java solution using DP O(n^2)


  • 1
    Z

    Straight forward dp solution in Java. We try to find all the prefixes such that either -

    • prefix contained in dictionary OR
    • the prefix itself can be broken into parts i.e. a subproblem we already solved in previous computation.

    In both cases we try to extend the prefix to right upto the length of the string. We use dp table to store results computed for each prefix string[0..i].

    public class Solution {
        public boolean wordBreak(String text, Set<String> dictionary) {
            int n = text.length();
    		if(n == 0){
    			return true;
    		}
    		
    		//dp[i] = true if there is a solution in prefix text[0..i]
    		boolean[] dp = new boolean[n];  
    		
    		//try all possible prefixes
    		for(int i = 0; i< n; i++){
    			//check from dp if current length prefix is a solution
    			//if not then the prefix should be present in dictionary
    			if(dp[i] == false && dictionary.contains(text.substring(0, i+1))){
    				dp[i] = true;
    			}
    			
    			//if this prefix contains in dictionary the try to extend the prefix up to end of the string
    			if(dp[i] == true){
    				for(int j = i+1; j < n; j++){
    					//check id dp[j] already computed to a solution , 
    					//other wise we need to check if text[i+1..i] contains in the dict.
    					//so that we can create a longer prefix text[0..j]
    					if(dp[j] == false){
    						dp[j] = dictionary.contains(text.substring(i+1, j+1));
    					}
    				}
    			}
    		}
    		
    		
    		return dp[n-1];
        }
    }

Log in to reply
 

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