首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。