首页 > 代码库 > LintCode-Word Segmentation

LintCode-Word Segmentation

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example

Given

s = "lintcode",

dict = ["lint", "code"].

Return true because "lintcode" can be segmented as "lint code".

Analysis:

It is a DP problem. However, we need to use charAt() instead of substring() to optimize speed. Also, we can first check whether each char in s has appeared in dict, if not, then directly return false. (This is used to pass the last test case in LintCode).

Solution:

 1 public class Solution { 2     /** 3      * @param s: A string s 4      * @param dict: A dictionary of words dict 5      */ 6     public boolean wordSegmentation(String s, Set<String> dict) { 7         if (s.length()==0) return true; 8          9         char[] chars = new char[256];10         for (String word : dict)11             for (int i=0;i<word.length();i++)12                 chars[word.charAt(i)]++;13 14         for (int i = 0;i<s.length();i++)15             if (chars[s.charAt(i)]==0) return false;16 17         boolean[] d = new boolean[s.length()+1];18         Arrays.fill(d,false);19         d[0] = true;20         for (int i=1;i<=s.length();i++){21         StringBuilder builder = new StringBuilder();22             for (int j=i-1;j>=0;j--){23                 builder.insert(0,s.charAt(j));24                 String cur = builder.toString();25                 if (d[j] && dict.contains(cur)){26                     d[i]=true;27                     break;28                 }29             }30         }31 32         return d[s.length()];33 34     }35 }

 

LintCode-Word Segmentation