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".
别人很好的解题思路
https://www.nowcoder.com/questionTerminal/5f3b7bf611764c8ba7868f3ed40d6b2c
我的思路
package design; import java.util.HashSet; import java.util.Set; public class Solution { int len=999; int can[][] = new int[len+1][len+1]; int visit[][] = new int[len+1][len+1]; int Can(String s, Set<String> dict, int start, int endd) { if (dict.contains(s.substring(start, endd))) return 1; return 0; } int ok(String s, Set<String> dict, int start, int endd) { if (visit[start][endd] == 0) { visit[start][endd] = 1; if (Can(s, dict, start, endd) == 1) { can[start][endd] = 1; } else { for (int i = start + 1; i < endd; i++) { can[start][i] = ok(s, dict, start, i); can[i][endd] = ok(s, dict, i , endd); if (can[start][i] == 1 && can[i][endd] == 1) { can[start][endd] = 1; break; } } } } return can[start][endd]; } public boolean wordBreak(String s, Set<String> dict) {
if(s==null||dict==null||s.isEmpty()||dict.isEmpty()) return false; //容易遗漏 len = s.length(); if(ok(s,dict,0,len)==1) return true; return false; } public static void main(String args[]) { Set<String> a=new HashSet<String>(); String s="sad"; a.add("sa"); a.add("d"); Solution ss=new Solution(); } }