首页 > 代码库 > [leetcode]Word Break
[leetcode]Word Break
问题描述:
Given a string s and a dictionary of wordsdict, 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"
.
基本思想:
动态规划思想: 保存每个子串S(i,j)是否可分的信息。从小到大构建可分性表格。
代码:
public boolean wordBreak(String s, Set<String> dict) { //java if(s.isEmpty()) return true; if(dict.contains(s)) return true; int len = s.length(); int [][] record = new int[len+1][len+1]; for(int i=0; i<=len; i++) record[i][i]=1; for(int step=1; step<=len; step++) { for(int j=step; j<=len; j++) { int i=j-step; if(dict.contains(s.substring(i,j))) { record[i][j]=1; continue; } for(int k=i+1; k<j; k++) { if(record[i][k]==1 && record[k][j]==1) { record[i][j] = 1; break; } } } } if(record[0][len] == 1) return true; else return false; }
[leetcode]Word Break
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。