16ms Java DP+DFS Solution


  • 5
    C
    public class Solution {
        List<String> result;
        public List<String> wordBreak(String s, Set<String> wordDict) {
            result = new ArrayList<String>();
            int n = s.length();
            List<Integer>[] pointer = new List[n];
            for(int i=0;i<n;i++) pointer[i]=new ArrayList<Integer>();
            //DP to record break point
            for(int i=0;i<n;i++){
                for(int j=0;j<=i;j++){
                    if(wordDict.contains(s.substring(j,i+1))&&(j==0||pointer[j-1].size()>0))
                        pointer[i].add(j);
                }
            }
            helper(pointer, s, n-1, "");
            return result;
        }
        //DFS to retrieve results
        public void helper(List<Integer>[] pointer, String s, int i, String pattern){
            if(i<0){
                result.add(pattern);
                return;
            }
            for(Integer item:pointer[i]){
                String nextPattern = pattern.length()==0?s.substring(item,i+1):s.substring(item,i+1)+" "+pattern;
                helper(pointer, s, item-1, nextPattern);
            }
        }
    }

  • 0
    N

    OMG.........Really AWESOME!!! Can you explain more specifically?


  • 0
    S

    Not really, it will run fore ever for the following case:
    String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    String dict[] = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};


Log in to reply
 

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