I think my algorithm is correct and use o(n) time cost, but it always runs out of time limit, can someone tell me why?


  • 0
    M

    public boolean wordBreak(String s, Set<String> dict) {

    	Set<String> dictCopy = new HashSet<String>();
    	for (String dic : dict) {
    		if (s.contains(dic)) {
    			dictCopy.add(dic);
    		}
    	}
    
    	boolean result = false;
    
    	for (String dic : dictCopy) {
    		String[] arr = s.split(dic);
    
    		if (arr.length == 0) {
    
    			result = true;
    			break;
    		}
    
    		boolean subResult = true; // 标记子列表是否可以被分割
    
    		for (String a : arr) {
    			if (a.equals("")) {
    				continue;
    			}
    			if (!a.equals(s)) {
    				if (!this.wordBreak(a, dictCopy)) {
    					subResult = false;
    					break;
    				}
    			} else {
    
    				subResult = false;
    				break;
    			}
    		}
    
    		if (subResult) {
    			result = true;
    			break;
    		}
    
    	}
    
    	return result;
    }

  • 0
    G

    The biggest problem is that you didn't store the result of your substring.

    For example you have

    s="abcdefg"

    dic=["abc", "de", "ab", "cde"]

    Your program tries to break it into abc|de|fg and find fg is not a word. Then the program tries to break s into ab|cde|fg, and again need to find whether fg is a word or not.

    Your program runs on fg twice, which is unnecessary.


  • 0
    M

    Thank you for your replay. But I think it's not the point. The way which I use to solve the problem is not about o(n) costs in time, but about o(n*n). In some cases, it really take lots of time in calculating.


  • 1
    S

    Going through each string in dictionary is really costly. The size of dictionary could be and should be extremely huge. That's why when encountering a dict problem, we are always using dict.contains() to avoid run through the dictionary.


Log in to reply
 

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