Java: Word Break

Thought Process

The Word Break problem requires determining if a string can be segmented into space-separated words from a given dictionary. Here are two approaches:

Approach 1: Dynamic Programming - First, we create a states array where states[i] indicates if substring s[0...i-1] is breakable or not. At each position, we check all dictionary words that could end there. If we find a word that matches and connects to a previous breakable state, we update the state accordingly. Finally, states[len] indicates whether a string of length 'len' is breakable or not.

Approach 2: Trie with Memoization - Here, we build a Trie from the dictionary words for efficient prefix searches. Further, we perform DFS (with memoization) & store results of subproblems in a map to avoid recomputation. After each valid word match, recursively check if the remaining substring can be broken or not.

Approach 1: Dynamic Programming 

class Solution {
    public boolean wordBreak(String str, List<String> wordDict) {
        
        int len = str.length();

        // states[i] tell whether string till ith index is breakable or not.
        boolean[] states = new boolean[len+1];
        states[0] = true;
        for(int i=1;i<=len;i++){

            for(int j=0;j<wordDict.size();j++){

                String s1 = wordDict.get(j);
                int len1  = s1.length();
                int start = i-len1; // Starting position of the substring.

                if(start>=0){

                    String s2 = str.substring(start,start+len1);
                    // Condition: Previous part of string till length = start is breakable
                    // & current substring i.e. s2 is contained in the dictionary.
                    if(states[start]==true && s1.equals(s2))
                        states[start+len1]=true;
                }
            }
        }
        return states[len];
    }
}

Approach 2: Trie with Memoization 

// Basic Trie Node
class TrieNode{

    TrieNode[] children;
    boolean isEndOfWord;

    TrieNode(){
        children = new TrieNode[26];
        isEndOfWord = false;
    }
}
class Solution {

    // Memorize the solution
    // It will tell whether a substring starting from ith character is breakable or not.
    Map<Integer,Boolean> memo = new HashMap<>();
    public void insert(TrieNode root, String str ){

        // Simply insert the string into Trie
        TrieNode copy = root;
        for(int i=0;i<str.length();i++){

            char ch = str.charAt(i);
            if(copy.children[ch-'a']==null)
                copy.children[ch-'a'] = new TrieNode();

            copy = copy.children[ch-'a'];
        }
        copy.isEndOfWord = true;
    }
    public boolean search(TrieNode root, String str, int start){

        if(start == str.length())
            return true;

        if(memo.containsKey(start))
            return memo.get(start);

        TrieNode copy = root;
        for(int i=start;i<str.length();i++){

            char ch = str.charAt(i);
            if(copy.children[ch-'a']==null){
                memo.put(start,false);
                return false;
            }
            copy = copy.children[ch-'a'];
            if(copy.isEndOfWord == true){

                // If search comes true then return true else continue iterating 
                // the string.
                if(search(root,str,i+1)){
                    memo.put(start,true);
                    return true;
                }
                    
            }
        }
        // Consider a case when Trie is sequence of 10 a's and our string is "aaa"
        memo.put(start,false);
        return false;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        
        TrieNode root = new TrieNode();
        for(int i=0;i<wordDict.size();i++){

            String str = wordDict.get(i);
            insert(root,str);
        }

        boolean isBreakable = search(root,s,0);
        return isBreakable;
    }
}

Code Complexity

Time Complexity: O(n3) for DP & O(n2) for Trie

DP approach has nested loops O(n2) with substring operations O(n). Trie approach reduces to O(n2) with memoization.

Space Complexity: O(n + m*k)

DP uses O(n) space, Trie uses additional space for dictionary storage where 'n' is string length, 'm' is dictionary size, and 'k' is average word length.

Code copied!