My DP solution in Java


  • 0
    T

    pretty standard approach, though a bit long

    public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        
    
        char ss[] = s.toCharArray();
        Set<char[]> dict2 = new HashSet<char[]>();
        for(String d : dict) {
            dict2.add(d.toCharArray());
        }
        
        List<Integer> ok [] = new ArrayList[ss.length];
        for(int i=0;i<ok.length;i++)
            ok[i] = new ArrayList<Integer>();
        for(int i=0;i<ss.length;i++) {
            for(char[] d: dict2) {
                int start = i-d.length+1;
                if ( start>=0 && matches(ss, start, i, d) && ( start -1 == -1 || ok[start-1].size()>0)) {
                    ok[i].add(start-1);
                }
                    
            }
        }
        
        return trace(ss, ss.length -1, ok);
    }
    
    
    List<String> trace(char [] ss, int end, List<Integer> prevs[]) {
        List<String > result = new ArrayList<String>();
    
        for(Integer prev:prevs[end]) {
            if (prev <0)
            result.add(new String(ss,prev+1,end-prev));
            else
            result.addAll(extend(trace(ss, prev, prevs), new String(ss, prev+1, end-prev)) );
        }
        return result;
    }
    List<String> extend(List<String> base, String newseg) {
        List<String> result = new ArrayList<String>();
        for(String b:base) {
            result.add(b + " " + newseg);
        }
        
        return result;
    }
    
    boolean matches(char[] s, int start, int end, char[] d) {
        if (d.length != end - start +1) return false;
        
        for(int i=start;i<=end;i++)
            if (s[i] != d[i-start]) return false;
        return true;
    }
    

    }


Log in to reply
 

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