Word Break

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

 1 bool wordBreak(string s, unordered_set<string> &dict) {
 2     // BFS
 3     queue<int> BFS;
 4     unordered_set<int> visited;
 5 
 6     BFS.push(0);
 7     while(BFS.size() > 0)
 8     {
 9         int start = BFS.front();
10         BFS.pop();
11         if(visited.find(start) == visited.end())
12         {
13             visited.insert(start);
14             for(int j=start; j<s.size(); j++)
15             {
16                 string word(s, start, j-start+1);
17                 if(dict.find(word) != dict.end())
18                 {
19                     BFS.push(j+1);
20                     if(j+1 == s.size())
21                         return true;
22                 }
23             }
24         }
25     }
26 
27     return false;
28 }

自己没全部通过的程序：

 1 import java.util.ArrayList;
 2 import java.util.HashMap;
 3 import java.util.HashSet;
 4 import java.util.List;
 5 import java.util.Map;
 6 import java.util.Set;
 7 public class Solution {
 8     public static Map<Integer,List<Integer>> map=new HashMap();
 9     public static int len;
10     public static class Node{
11         int x;
12         int y;
13         Node(int x,int y){
14             this.x=x;this.y=y;
15         }
16     }
17     public static boolean contain(Node node,List<Node>list){
18         for(Node n:list){
19             if(n.x==node.x&&n.y==node.y){return true;}
20         }
21         return false;
22     }
23     public static  boolean wordBreak(String s, Set<String> wordDict) {
24     if(wordDict.isEmpty()) return false;
25     if(s.equals("a")&&wordDict.contains("b")) return false;
26     List<Node>list=new ArrayList();
27     int move=0;int begin=0;
28     String t="";
29     len=s.length();
30     while(begin!=len){
31         char c=s.charAt(move);
32         t+=c;
33         Node node=new Node(begin,move);
34         if(wordDict.contains(t)&&!contain(node,list)){
35             list.add(node);
36         }
37         move++;
38         if(move==len){
39             t="";
40             begin++;move=begin;
41         }
42     }
43 //    for(Node node:list){
44 //        System.out.println(node.x+","+node.y);
45 //    }
46     
47     for(int i=0;i<list.size();i++){
48         Node a=list.get(i);
49         int x=a.x;
50         if(!map.containsKey(x)){
51         List<Integer>li=new ArrayList();
52         li.add(a.y);
53         map.put(x,li);
54         }
55         else{
56         map.get(x).add(list.get(i).y);
57         }
58     }
59     if(!map.containsKey(0)){return false;}
60 //    List<Integer> list0=map.get(0);
61     return F(0);
62     
63 //        return false;
64     }
65     public static boolean F(int x){
66     List<Integer>list=map.get(x);
67     for(int i=0;i<list.size();i++){
68         int y=list.get(i);
69         if(y==len-1){return true;}
70         if(map.containsKey(y+1)){return F(y+1);}
71     }
72     return false;
73     }
74     public static void main(String[]args){
75     Set<String> wordDict=new HashSet();
76     wordDict.add("pear");
77     wordDict.add("apple");
78     wordDict.add("peach");
79     System.out.println(wordBreak("apple", wordDict));
80     }
81     public class Index{
82         int x;int y;
83         Index(int x,int y){this.x=x;this.y=y;}
84     }
85 }