Leetcode Q : Letter Case Permutation (Java)

February LeetCoding Challenge 2021 ( Week 3, day 16 )

Q : Letter Case Permutation

 

문제 해설

 

주어진 문자열 안의 각각의 문자는 대문자, 혹은 소문자로 변경 가능하다.

생성가능한 문자열을 List에 저장하여 반환하라. 반환하는 문자열의 순서는 무관.

 

 제한 사항

 - 문자열 길이는 1 이상 12 이하

 - 문자열은 문자와 숫자로만 이루어져있다

 

 

문제 풀이

 

재귀 함수를 이용하여 문제를 해결할 수 있다.

 

 

깊이가 0일때

 

문자열 : a1b2

 

 

깊이가 1일때

 

문자 a 는 a 또는 A 가 될 수 있으므로

두 가지 경우의 수로 나누어진다.

 

문자열 : "a1b2" , "A1b2"

 

 

깊이가 2일때

 

문자는 1이므로 아무일도 일어나지 않는다.

 

문자열 : "a1b2" , "A1b2"

 

 

깊이가 3일때

 

문자 b 는 b 또는 B 가 될 수 있으므로

두 개의 문자열이 각각 두 가지 경우의 수로 나누어진다.

 

"a1b2" -> "a1b2" , "a1B2"

"A1b2" -> "A1b2", "A1B2

 

문자열 : "a1b2", "a1B2", "A1b2", "A1B2"

 

  

 

 

결과

Runtime : 1 ms , Your runtime beats 100.00% of java submissions

Memory Usage : 39.7 MB , Your memory usage beats 68.40% of java submissions

 

 

 

결론

경우의 수를 나열하는 방법(brute-force)을 구현할때 재귀 알고리즘을 적용하면 답을 빠르게 구할 수 있다.