-
Notifications
You must be signed in to change notification settings - Fork 5
/
WordBreak.java
72 lines (68 loc) · 2.42 KB
/
WordBreak.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*https://practice.geeksforgeeks.org/problems/word-break-part-23249/1*/
class Solution
{
static HashSet<String> set;
static List<String> result;
static String getList(String s, int n, int[] table)
{
StringBuilder sb = new StringBuilder("");
int i = 0, j = 1;
while (i <= n && j <= n)
{
while (table[j] != 1) ++j;
sb.append(s.substring(i,j));
sb.append(" ");
i = j;
j = j+1;
}
return sb.substring(0,sb.length()-1);
}
static void wordBreakSolver(int[] table, String s, int n, int index, int loop)
{
//if the entire string has been processed
if (index > n)
{
//add the current table to the result if the last index is 1
if (table[table.length-1] == 1) result.add(getList(s,n,table));
}
else
{
//from loop starting point till current index
for (int j = loop; j <= index && index <= n; ++j)
{
//if the substring till jth index has been checked
//and from j to index substring is present in the dictionary
if (table[index] == 0 && table[j] > 0 && set.contains(s.substring(j,index)))
{
table[index] = 1; //backtracking step - 1
//start the loop from the current index and increase index to 1
wordBreakSolver(table,s,n,index+1,index); //backtracking step - 2
table[index] = 0; //backtracking step - 3
}
else
{
//restart j and increase the index
j = loop-1;
++index;
}
}
}
}
static List<String> wordBreak (int m, List<String> dict, String s)
{
//add the dictionary words to a hashset
set = new HashSet<String>();
for (String str : dict) set.add(str);
//create the result list
result = new ArrayList<String>();
/*
create the board for backtracking and store 1 at 0th index
(complete reference on Dynamic Programming - WordBreak.java)
*/
int[] table = new int[s.length()+1];
table[0] = 1;
//start with 0th position as the loop starting point and 0th position as the index
wordBreakSolver(table,s,s.length(),0,0);
return result;
}
}