国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 【Leetcode】Word Break

【Leetcode】Word Break

来源:程序员人生   发布时间:2016-06-12 15:53:14 阅读次数:1055次

题目链接:https://leetcode.com/problems/word-break/

题目:

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".

思路:

res[i] = res[j]&wordDict.contains(s.subString(j,i));

从0~i的字符串能用单词表示 取决于 是不是存在从0~j的字符串能用单词表示,且从j~i是1个单词。j<i

算法:

  1. public boolean wordBreak(String s, Set<String> wordDict) {  
  2.         boolean res[] = new boolean[s.length() + 1];// 表示到i为止的子串能否用单词表示  
  3.         res[0] = true;  
  4.         for (int i = 0; i <= s.length(); i++) {  
  5.             for (int j = 0; j < i; j++) {  
  6.                 if (res[j] && wordDict.contains(s.substring(j, i))) {  
  7.                     res[i] = true;  
  8.                     break;  
  9.                 }  
  10.             }  
  11.         }  
  12.         return res[s.length()];  
  13.     }  

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生