[Java] LeetCode 17번 Letter Combinations of a Phone Number

[Java] LeetCode 17번 Letter Combinations of a Phone Number

옛날 피처폰에 숫자위치에 있는 알파벳들의 가능한 조합을 모두 출력하는 문제이다.

이런 조합의 문제에서는 재귀호출을 통해서 쉽게 해결할 수 있다.

재귀 함수를 작성할 때 중요한 포인트는 언제 함수가 종료되는지 잘 명시하는 것이다. digits의 길이가 0이 되면 비어있는 리스트를 리턴하고, 1이라면 map에서 조회하여 리턴한다.

이외의 경우에는 첫번째 숫자와 나머지 문자를 이어서 정답에 추가하여 리턴한다.

class Solution { Map> map = new HashMap<>(); { map.put("2", List.of("a", "b", "c")); map.put("3", List.of("d", "e", "f")); map.put("4", List.of("g", "h", "i")); map.put("5", List.of("j", "k", "l")); map.put("6", List.of("m", "n", "o")); map.put("7", List.of("p", "q", "r", "s")); map.put("8", List.of("t", "u", "v")); map.put("9", List.of("w", "x", "y", "z")); } public List letterCombinations(String digits) { List answer = new ArrayList<>(); if (digits.length() == 0) { return answer; } else if (digits.length() == 1) { return map.get(digits); } String digit = digits.substring(0, 1); List str = this.map.get(digit); List rightStr = letterCombinations(digits.substring(1)); for (int i = 0; i < str.size(); i++) { String s = str.get(i); for (int j = 0; j < rightStr.size(); j++) { String rs = rightStr.get(j); answer.add(s + rs); } } return answer; } }

반응형

from http://blue-jay.tistory.com/73 by ccl(A) rewrite - 2021-09-26 22:27:31