Leetcode: Word Break

This question is asked at Facebook, Amazon, Bloomberg, and Microsoft.

Given a non-empty string s and a dictionary wordDict containing nonempty words, determine if S can be segmented into a space separated sequences of one more more dictionary words. Notice that the same word in the dictionary may be reused multiple times in the segmentation, and you may assume that the dictionary does not contain duplicate words. 

Here are examples: 

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]

Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]

Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".

             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

Output: false

Surprisingly, this is a dynamic programming problem.

Let's first code up the brute force solution. 

public class Solution {

    public boolean wordBreak(String s, List<String> dict) {

             return wordBreakHelper(s, dict, 0);

    }

 

    public boolean wordBreakHelper(String s, List<String> dict, int start){ 

        if(start == s.length()) {

            return true;

        }

        for(String a: dict){

            int len = a.length();

            int end = start+len;        

            if(end > s.length()) {

                continue;

            }

            if(s.substring(start, start+len).equals(a)){

                if(wordBreakHelper(s, dict, start+len)){

                    return true;

                }

            }      

        }

        return false;

    }

}

Basically, this approach checks all of the strings in the for loop, and all of the substrings are recursively called as a result. However, this is not the most efficient way. We can also use dynamic programming to solve this problem.

We define an array t[] such that t[i] == true can be segmented using a dictionary. 

public class Solution {

    public boolean wordBreak(String s, List<String> dict) {

        boolean[] t = new boolean[s.length() + 1];

        //start the dp process

        t[0] = true;

        for(int i = 0; i < s.length(); i++) {            

            //move to the next word that is true and go from there.

            if(t[i] == false) {

                continue;

            }

            for (String a: dict) {

                int len = a.length();

                int end = i + len;

                if(end > s.length()) {

                    continue;

                }

                //add the length of the word and compare

                if(s.substring(i, end).equals(a)) {

                    t[end] = true;

                }

            }

    }

    //return the end of the dynamic programming table.

    return t[s.length()];

    }

}