Saturday, December 13, 2014

Word Break

Typical DP, finally! My initial goal is reviewing DP today. But both of the previous two problems had a better solution than DP.

i: a potential break point;
j: the length of the substring need to be checked, j must be smaller than the length of the longest word in the dictionary
canbeBreak[i]: if the i-th position is a break
canbeBreak[i] = canbeBreak[i - j] && dict.contains(i - j, i): i is a break point if there exists a cut at i -  j that is also a break point, and s.substring(i - j, i) is in the dictionary. 


public class Solution {
    public boolean wordBreak(String s, Set dict) {
        if (s == null || dict.isEmpty())
            return false;
        int maxlength = getMaxLength(dict);
        
        //canbeBreak[i]: check if i-th position is a break
        boolean[] canbeBreak = new boolean[s.length() + 1];
        canbeBreak[0] = true;
        
        for (int i = 1; i <= s.length(); i++)
        {
            canbeBreak[i] = false;
            for (int j = 1; j <= i && j <= maxlength; j++)
            {
                //i - j, the break position, if the first "half" of the substring is not in the dictionary
                // continue
                if(!canbeBreak[i - j])
                    continue;
                String word = s.substring(i - j, i);
                if (dict.contains(word))
                {
                    canbeBreak[i] = true;
                    break;
                }
            }
            
        }
        return canbeBreak[s.length()];
        
    }
    //if the length of the substring is larger than the longest word in the dictionary, there is no need to check
    private int getMaxLength(Set dict)
    {
        int maxlength = 0;
        for (String word : dict)
            maxlength = Math.max(maxlength, word.length());
        return maxlength;
    }
}

No comments:

Post a Comment