Accepted Java solution backtracking. But what's the difference with front-tracking?


  • 10
    J

    This is the accepted solution, which might be the "backtracking" algorithm. It starts to try the word from the backend.

    public static List<String> wordBreak(String s, Set<String> dict) {
    	List<String> words = new ArrayList<String>();
    	int len = s.length();
    	for (int i = len -1; i >= 0; i--) {
    		String last = s.substring(i, len);
    		if (dict.contains(last)) {
    			if (i == 0) {
    				words.add(last);
    			} else {
    				String remain = s.substring(0, i);
    				List<String> remainSet = wordBreak(remain, dict);
    				if (remainSet != null) {
    					for (String item : remainSet) {
    						words.add(item + " " + last);
    					}
    				}
    			}
    		}
    	}
    	return words;
    }
    

    It should be the same if it starts from the front, like following. (front-tracking is my invented word, maybe)

    public static List<String> wordBreakFront(String s, Set<String> dict) {
    	List<String> words = new ArrayList<String>();
    	
    	int len = s.length();
    	for (int i = 1; i <= len; i++) {
    		String front = s.substring(0, i);
    		if (dict.contains(front)) {
    			if (i == len) {
    				words.add(front);
    			} else {
    				String remain = s.substring(i, len);
    				List<String> remainSet = wordBreak(remain, dict);
    				if (remainSet != null) {
    					for (String item : remainSet) {
    						words.add(front + " " + item);
    					}
    				}
    			}
    		}
    	}
    	return words;
    }
    

    But actually it is not!!!
    The later is not accepted for lower efficiency.

    But Why?


  • 0
    J

    Actually these two algorithm are the same. Please note I have initiated another question here, it is already clarified. http://stackoverflow.com/questions/26299381/is-it-mandatory-for-backtracking-algorithm-to-start-from-back?noredirect=1#comment41272248_26299381


  • 5
    F

    I would say that there is indeed no difference between them. But both of the codes are only recursion instead of DP, which makes it possible to be very inefficient in some cases.

    How about storing the result of each recursion in a HashMap and reducing unnecessary recursions?

    public class Solution {
    
        Map<String, List<String>> results = new HashMap<String, List<String>>();
    
        public List<String> wordBreak(String s, Set<String> dict) {
            List<String> words = new ArrayList<String>();
    
            int len = s.length();
            for (int i = 1; i <= len; i++) {
                String front = s.substring(0, i);
                if (dict.contains(front)) {
                    if (i == len) {
                        words.add(front);
                    } else {
                        String remain = s.substring(i, len);
                        List<String> remainSet = results.containsKey(remain) ? 
                                results.get(remain) : wordBreak(remain, dict);
                        if (remainSet != null) {
                            for (String item : remainSet) {
                                words.add(front + " " + item);
                            }
                            results.put(remain, remainSet);
                        }  
                
                    }
                }
            }
            return words;
        }
    }
    

    Accepted.


  • 0
    J

    Could you refine your code? Because it cannot compile. Where is the definition of results? I found both "wordBreakFront" and "wordBreak".


  • 0
    F

    Results is initialized outside the function if you don't wanna make it a parameter.


  • 9
    Y

    I am thinking it is because of the test case "aaaaa...ab". The first one is passed is simply because you can not find any word in dict ending with "b" in the loop. So, for this case, there is no such time limit error. The second case, you have to start from beginning "aaaaaaa...", and then, time limit error comes.

    If there is a test case "baaaaaaaaaa...a", your first test might not be able to pass the OJ.


  • 1
    X

    Backtracking does not mean track from the back


  • 0

    Thanks so much for pointing this out. I have added the test case so both mentioned solutions get Time Limit Exceeded now. Thanks!


  • 0

    You are right. I have just added the test case "baaaaaa...a" and both solutions get time limit exceeded.


  • 0
    T

    @FreeTymeKiyan When I use "if (!remainSet.isEmpty())" instead of "if (remainSet != null)", I got TLE. Could not figure out why I got TLE.


Log in to reply
 

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