Beat 97.31, No Recursion


  • 0
    T

    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) {
                            dp[i].pst.add(s.substring(j, i));
                        } else {
                            for(String word: dp[j].pst) {
                                dp[i].pst.add(word + " " + s.substring(j, i));
                            }
                        }
                    }
                }
            }
            
            return dp[s.length()].pst;
        }
    }
    

Log in to reply
 

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