# I think my algorithm is correct and use o(n) time cost, but it always runs out of time limit, can someone tell me why?

• public boolean wordBreak(String s, Set<String> dict) {

``````	Set<String> dictCopy = new HashSet<String>();
for (String dic : dict) {
if (s.contains(dic)) {
}
}

boolean result = false;

for (String dic : dictCopy) {
String[] arr = s.split(dic);

if (arr.length == 0) {

result = true;
break;
}

boolean subResult = true; // 标记子列表是否可以被分割

for (String a : arr) {
if (a.equals("")) {
continue;
}
if (!a.equals(s)) {
if (!this.wordBreak(a, dictCopy)) {
subResult = false;
break;
}
} else {

subResult = false;
break;
}
}

if (subResult) {
result = true;
break;
}

}

return result;
}``````

• The biggest problem is that you didn't store the result of your substring.

For example you have

s="abcdefg"

dic=["abc", "de", "ab", "cde"]

Your program tries to break it into `abc|de|fg` and find `fg` is not a word. Then the program tries to break s into `ab|cde|fg`, and again need to find whether `fg` is a word or not.

Your program runs on `fg` twice, which is unnecessary.

• Thank you for your replay. But I think it's not the point. The way which I use to solve the problem is not about o(n) costs in time, but about o(n*n). In some cases, it really take lots of time in calculating.

• Going through each string in dictionary is really costly. The size of dictionary could be and should be extremely huge. That's why when encountering a dict problem, we are always using dict.contains() to avoid run through the dictionary.

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