# Always have a problem that need lots of memory to remember the path

• I always find it difficult to solve this kind of problem: whether some pattern is followed and return all the valid result. My solution is combining the "true or false" algorithm with an array that can remember the path I take, and usually, this path will end with false, but I have to save them in the memory before I know this path is actually invalid. On the other hand, when I am in old state j and find myself match the pattern, I want to add i to j, but I cannot add it directly because other i might also start from this j.

For example:
Suppose we already know the path:
0->3->6->8
And we find both i = 10 and i = 12 can be the next path, so I have to copy the entire path from the last state to current:
0->3->6->8 COPY to:
0->3->6->8
0->3->6->8
And add 10 and 12 at the end:
0->3->6->8->10
0->3->6->8->12

my method is so stupid that needs copy all the sub matched path every time, I looked at some TOP solutions but find that most of them use recursive method(And I think this way we will not have to copy all the finally invalid path? Because we are starting from bottom, and keep calling function until we reach the end), but I just want to know is there any way to resolve this "copy and add new path element" problem?
(Or for the path problem bottom-up method is preferred?)

This is my stupid code for handling path copy, but I am confused about its performance because it only takes 10ms beats 97%, I think this is not a very good solution for copy problem:

``````public class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
if (s.length() == 0 || wordDict.size() == 0) return new ArrayList<String>();
Set<String> dic = new HashSet<String>();
int max = wordDict.get(0).length();
int min = max;
for (String word: wordDict) {
if (word.length() < min) {
min = word.length();
} else if (word.length() > max) {
max = word.length();
}
}
boolean[] canBreak = new boolean[s.length() + 1];
if (!isWordBreak(s, dic, min, max)) return new ArrayList<String>();

List<List<List<Integer>>> resArray =
new ArrayList<List<List<Integer>>>(s.length() + 1);
for (int i = 0; i < s.length() + 1; i++) {
}

canBreak[0] = true;
resArray.set(0, new ArrayList<List<Integer>>());
for (String word: wordDict) {
int n = word.length();
if (min > word.length()) {
min = n;
} else if (max < word.length()) {
max = n;
}
}

for (int i = 1; i < s.length() + 1; i++) {
int n = Math.max(i - max, 0);
for (int j = Math.max(i - min, 0); j >= n; j--) {
if (canBreak[j] && dic.contains(s.substring(j, i))) {
canBreak[i] = true;
List<List<Integer>> prevIdxListArray = resArray.get(j);
List<List<Integer>> currIdxListArray = resArray.get(i);
if (currIdxListArray == null) {
currIdxListArray = new ArrayList<List<Integer>>();
for (List<Integer> prevIdxList: prevIdxListArray) {
List<Integer> listI = new ArrayList<Integer>();
for (int idx: prevIdxList) {
}
}
resArray.set(i, currIdxListArray);
} else {
for (List<Integer> prevIdxList: prevIdxListArray) {
List<Integer> listI = new ArrayList<Integer>();
for (int idx: prevIdxList) {
}
}
}
}
}
}

List<String> res;
if (canBreak[s.length()]) {
List<List<Integer>> idxListArray = resArray.get(s.length());
res = new ArrayList<String>(idxListArray.size());
for (List<Integer> idxList: idxListArray) {
StringBuilder sb = new StringBuilder();
int start = 0;
for (int i = 1; i < idxList.size(); i++) {
int end = idxList.get(i);
sb.append(s.substring(start, end) + " ");
start = end;
}
sb.setLength(sb.length() - 1);
}
} else {
res = new ArrayList<String>();
}

return res;
}

private boolean isWordBreak(String s, Set<String> dic, int min, int max) {
boolean[] canWordBreak = new boolean[s.length() + 1];
canWordBreak[0] = true;
for (int i = 1; i < s.length() + 1; i++) {
// Since we know the max length and min length of dic's word,
// we can limit the search range
int n = Math.max(i - max, 0);
for (int j = Math.max(i - min, 0); j >= n; j--) {
// Every time check stiring 0...j and j...i is breakable,
// if so 0......i is breakable
if (canWordBreak[j] && dic.contains(s.substring(j, i))) {
canWordBreak[i] = true;
break;
}
}
}
// The last one in the array is answer
return canWordBreak[s.length()];
}
}
``````

Thanks a lot!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.