[LeetCode] 784. Letter Case Permutation - 문제풀이

Description

주어진 문자열에서 대소문자를 변경 하여 가능한 순열 목록을 반환하는 문제입니다.

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

Example 1:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

Input: s = "3z4"
Output: ["3z4","3Z4"]

Constraints:

• 1 <= s.length <= 12
• s consists of lowercase English letters, uppercase English letters, and digits.

Solution 1. Backtracking

public List<String> letterCasePermutation(String s) {
    List<String> result = new ArrayList<>();
    backTracking(result,s.toCharArray(),0);
    return result;
}

private void backTracking(List<String> result, char[] chars, int i){
    if(i == chars.length){ // ending case
        result.add(new String(chars));
        return;
    }

    char c = chars[i];
    if (Character.isLetter(c)) {
        backTracking(result,chars,i+1);
        if(c >= 'a' && c <= 'z'){
            chars[i] = Character.toUpperCase(c);
            backTracking(result,chars,i+1);
        }else if(c >= 'A' && c <= 'Z'){ // lowercase
            chars[i] = Character.toLowerCase(c);
            backTracking(result,chars,i+1);
        }
    }else{
        backTracking(result,chars,i+1);
    }

}

백트래킹(Backtracking)을 통해 영어가 나올 경우 가능한 경우의 수(대소문자) 브랜치를 2개로 늘려가며 최종 인덱스(length)와 일치할 경우 해당 값을 반환합니다.

Reference

Letter Case Permutation - LeetCode

LeetCode, Algorithm, String, Hash Table, LinkedList, Depth-First Search, Breadth-First Search, Matrix, TwoPoint, Array, Recusion, 릿코드, 알고리즘, 코딩테스트, 코테, 문제풀이

Binary Tree, Recusion, 전위순회, inorder-traversal

중위순회, inorder-traversal, 후위순회, postorder-traversal,