역 추적 알고리즘이 반드시 뒤에서 시작해야합니까?

Question

backtracking 알고리즘으로 wordbreakII 문제 을 해결했습니다. 나는 정면에서 처리하려고하면

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); //get the last word and process the rest 
     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; 
} 

하면, 결과는 동일해야합니다 : 다음은 코드입니다.

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 { 
       //get the front word and process the rest. 
       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; 
} 

앞 추적 기능도 작동합니다 (올바른 출력을 생성 할 수 있음). 그러나 효율이 낮다는 것은 시간 제한 테스트에서 실패한 것입니다. 나중에이 경우에 실패

// 마지막으로 실행 입력 : "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", [ "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAAA", "AAAAAAA" "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"]

그래서 왜 뒤에서 시작하면 차이가 있는지 이해할 수 없습니까?

감사합니다.

Answer 1

두 경우 모두 최악의 경우 지수 적 시간 복잡성을 갖습니다. 첫 번째 단어는 성공했고 두 번째 단어는 실패했습니다 (입력 단어와 사전의 모든 단어를 뒤집 으면 첫 번째 단어가 너무 길게 작동합니다).