This is my accepted java version program, is there any better solution?


  • 8
    X

    This is my solution. I use DP- with a hashmap recording all the strings that are computed before.
    My idea is simple, just partition the string from the first character until the last character. Each time the string is divided into two parts: left and right. Only if the left string exists in the dict, we will try to get all of the combinations of the right string. And then form the list of combinations of the left and right.

    The time complexity is O(n^2). Is there any better run time solution?

    public class Solution {
    HashMap<String, List<String>> map= new HashMap<String, List<String>>();
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> list=new ArrayList<String>();
                
        if(map.containsKey(s)) return map.get(s);
        
        for(int i=1; i<=s.length();i++){
            String left=s.substring(0,i);
            String right=s.substring(i);
            if(dict.contains(left)){
                List<String> a=wordBreak(right, dict);
                for(String b:a){
                    list.add(left+" "+b);
                }
                if(right.length()==0) list.add(left);
            }
            
        }
    
        map.put(s, list);
        return list;
    }
    

    }


  • 8
    W

    You can't have an O(n^2) algorithm.
    The worst cases have 2^n solutions.
    The OJ test cases are just too easy.

    Try the input:
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa",
    "aaaaaaaaaaa","aaaaaaaaaaaa","aaaaaaaaaaaaa","aaaaaaaaaaaaaa","aaaaaaaaaaaaaaa",]


  • 0
    C
    	public static List<String> wordBreak2(String s, Set<String> dict) {
    	int n = s.length();
    	HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
    	String secStr = "";		
    	
    	for (int i = 0; i < n; i++) {
    		ArrayList<String> arrLisForLenI = new ArrayList<String>();
    		//get the string length i
    		String wordForLenI = s.substring(0, i + 1);
    		if(dict.contains(wordForLenI)) {
    			arrLisForLenI.add(wordForLenI);
    			map.put(i, arrLisForLenI);
    		}
    		//check the the existed word break string
    		for(int j : map.keySet()) {
    			secStr = s.substring(j + 1, i + 1);
    			//the right side of existed word break string
    			if(dict.contains(secStr)) {
    				for(String sentence : map.get(j)) {
    					sentence += " " + secStr;
    					arrLisForLenI.add(sentence);
    				}
    			}
    		}
    		if(!arrLisForLenI.isEmpty()) {
    			map.put(i, arrLisForLenI);
    		}				
    	}
    	return map.get(n - 1);
    }
    

    Why my code can't pass a, aa, aaa, aaaa... test? I run this case with your code and my code in my PC and get almost same running time. Could anyone help me improve my code?


  • 0
    F

    I ran you code on s="aaaaaaaaaaaaaaaaab" and dict=[a, aa,aaaa,aaaaaa]. It is indeed as fast. However the answer should be empty list [ ]. You answer is null. Maybe that is why.


  • 0
    F

    I added "static" in front of your second line i.e.

    static HashMap<String, List<String>> map= new HashMap<String, List<String>>();

    And suddenly I have a problem of exceeding time limit. I hope this is a bug in LeetCode.


  • 0
    P

    I think there is a problem in your code.
    In the leetcode test cases, the one I failed most is "aaaaaaaaaaaaaaaaaaa....aaaab" with dict = [a, aa, aaa, aaaa .... aaaaaaaa]. I always fail with TLE.
    In your solution, because you used recursion, so indeed it goes from b, ab etc to prevent the your list gets too large.

    If you try a test case with "baaaaaaaaaaaa....aaaa", your solution will take very long time. And it will finally end with Out of Memory error.


  • 0
    S

    I met the same situation here. Basically my solution is pretty much similar as above besides the "static" constraint put on the map.


  • 0
    Z

    I want to know why The time complexity is O(n^2)


Log in to reply
 

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