Find if a word can be constructed from the dictionary

Question

Anonymous · Accepted Answer

Non optimally, but laid out all possible solutions + complexities.

Anonymous · Answer

public boolean wordBreak(String s, List wordDict) {
        Set dict = new HashSet(wordDict);
        boolean[] f = new boolean[s.length() + 1];
        
        f[0] = true;
        for(int i=1; i <= s.length(); i++){
            for(int j=0; j < i; j++){
                if(f[j] && dict.contains(s.substring(j, i))){
                    f[i] = true;
                    break;
                }
            }
        }
        
        return f[s.length()];
    }

Anonymous · Answer

LeetCode Problem 139. Word Break

Meta

Meta Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches