大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 字符串按词典分割

字符串按词典分割

关键词:字符串词典字符串按词典分割  阅读(647) 赞(12)

[摘要]本文主要是对字符串按词典分割的讲解,希望对大家学习字符串按词典分割有所帮助。

  题目原型:

  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.

  For example, given

  s = "leetcode",

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

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

  思路:

  可以考虑用动态规划,用f(i,j)表示字符串S从i到j的子串是否可分割,则有:f(0,n) = f(0,i) && f(i,n),然后f(0,i)和f(i,n)又可以继续分割。

  public boolean wordBreak(String s, Set<STRING> dict)

  {

  if(dict.size()==0)

  return false;

  if(s.equals("")||s==null)

  return true;

  ArrayList<INTEGER> list = new ArrayList<INTEGER>();//存放能够被检索的字符串的位置

  int len = s.length();

  String str,strtemp;

  for(int i = len-1;i>=0;i--)

  {

  str = s.substring(i);

  if(dict.contains(str))

  {

  list.add(i);

  }

  else

  {

  //如果词典中不包含的话就在已经分割的字符串中找,比如字符串是"hello",而词典中有"hel"和"lo",那么就先匹配"lo",再匹配"hel"

  for(Integer index : list)

  {

  strtemp = s.substring(i, index);

  if(dict.contains(strtemp))

  {

  list.add(i);

  break;

  }

  }

  }

  }

  if(list.size()>0&&list.get(list.size()-1)==0)

  return true;

  else

  return false;

  }



相关评论