Forest Gump?

[LeetCode] Letter Combinations of a Phone Number-BackTracking 본문

카테고리 없음

[LeetCode] Letter Combinations of a Phone Number-BackTracking

code1010 2024. 3. 25. 21:30

 

 

문제 조건

숫자가 포함된 문자열이 주어지면 2-9숫자가 나타낼 수 있는 가능한 모든 문자 조합을 반환합니다.

전화 버튼과 마찬가지로 숫자를 문자로 매핑하는 방법은 다음과 같습니다. 1은 어떤 문자에도 매핑되지 않습니다.

입출력

 

 

 

 

INPUT 

digits = "23"

OUTPUT 

["ad","ae","af","bd","be","bf","cd","ce","cf"]

문제 접근

 

 

이런 그림으로 풀이되는 백트래킹 문제이다. 첫번째 숫자가 특정되면, 다른 번호에 매핑된 배열에 리프 노드를 한번씩 갔다와서

리스트에 넣어준다. 

 

 

문제 풀이

  public static void dfs(List<String> result, Map<Character,List<Character>> dic,String digits, int index, StringBuilder path) {

    //끝까지 탐색했으면 저장하고 리턴

    //인덱스가 digits길이와 같다는 것은 탐색이 끝났다는 뜻
    if (index == digits.length()) {
      result.add(String.valueOf(path));
      return;
    }
    //현재 숫자에 해당하는 모든 문자열 탐색
    //Map의 key는 해당 키(숫자)에 매핑된 캐릭터의 리스트
    //index를 1씩 키워가며 재귀적으로 탐색
    for (char c : dic.get(digits.charAt(index))) {
      dfs(result, dic, digits, index + 1, new StringBuilder(path).append(c));
    }
  }

  public static List<String> letterCombinations(String digits){

    //결과 저장 리스트 선언
    List<String> result = new ArrayList<>();

    //예외 처리
    if(digits.length() == 0) {return result;}

    //번호로 조합 가능한 문자 목록 구성

    Map<Character, List<Character>> dic = new HashMap<>();

    dic.put('2', List.of('a','b','c'));
    dic.put('3', List.of('d','e','f'));
    dic.put('4', List.of('g','h','i'));
    dic.put('5', List.of('j','k','l'));
    dic.put('6', List.of('m','n','o'));
    dic.put('7', List.of('p','q','r','s'));
    dic.put('8', List.of('t','u','v'));
    dic.put('9', List.of('w','x','y','z'));

    //현재 자리 0, 빈 문자열 이용 DFS탐색

    dfs(result, dic, digits, 0, new StringBuilder());
    return result;
  }

어려웠던 점

재귀함수 문제가 오랜만이라 유튜브를 참고했다. 해당 백트래킹에 필요한 트리를 도식화 하니 조금 더 이해가 됐다. 

트리에 리프노드에 대해서 하나씩 출력하게 되는 그림으로 형상화 하려고 한다.

 

참고 자료