# Beat 97.31, No Recursion

• Try to come up with a solution without recursion, here is my answer.

class Pair {
boolean isWord;
List<String> pst;
public Pair(boolean isWord) {
this.isWord = isWord;
pst = new ArrayList<>();
}
}
public class Solution {
public List<String> wordBreak(String s, Set<String> wordDict) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() == 0) {
return ans;
}

// word break I
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (String st : wordDict) {
max = Math.max(st.length(), max);
min = Math.min(st.length(), min);
}

boolean[] d = new boolean[s.length() + 1];
d[0] = true;

for (int i = 1; i <= s.length(); ++i) {
int end = (i - max) < 0?0: i - max;
for (int j = i - min; j >= end; --j) {
if (d[j] && wordDict.contains(s.substring(j, i))) {
d[i] = true;
break;
}
}
}

if (!d[s.length()]) {
return ans;
}

// dp, find answer
Pair[] dp = new Pair[s.length() + 1];
dp[0] = new Pair(true);

for(int i = 1; i <= s.length(); ++i) { // i 4
dp[i] = new Pair(false);
for(int j = i - 1; j >= 0; --j) {// j 0
if(dp[j].isWord && wordDict.contains(s.substring(j, i))) {
dp[i].isWord = true;
if(dp[j].pst.size() == 0) {
} else {
for(String word: dp[j].pst) {
dp[i].pst.add(word + " " + s.substring(j, i));
}
}
}
}
}

return dp[s.length()].pst;
}
}

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