1641. Count Sorted Vowel Strings

Count Sorted Vowel Strings - LeetCode

양의 정수 N이 주어질 때, 알파벳 소문자 모음 5개로 길이 N의 문자열을 만들고 그 가짓수를 반환한다.

이때 문자열을 구성하는 문자들은 사전 순으로 오름차순 정렬돼있는 문자열만 인정한다.

 

예시

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

 

 

접근법

입력되는 N은 최대 50이다. DFS로도 풀 수 있을 것 같은데...

하지만 재귀 없이 선형 탐색 정도의 시간 복잡도로도 문제를 해결할 수 있을 것 같았다.

 

1. 규칙을 이용한 구현

class Solution:
    def countVowelStrings(self, n: int) -> int:
        a, e, i, o, u = [1], [1], [1], [1], [1]

        for index in range(2, n + 1):
            a.append(a[-1] + e[-1] + i[-1] + o[-1] + u[-1])
            e.append(e[-1] + i[-1] + o[-1] + u[-1])
            i.append(i[-1] + o[-1] + u[-1])
            o.append(o[-1] + u[-1])
            u.append(u[-1])

        return a[-1] + e[-1] + i[-1] + o[-1] + u[-1]

규칙은 다음과 같다.

1. 어떤 문자열이 사전 순으로 정렬되어있다면 그 문자열의 부분 문자열도 사전 순 정렬되어있다.
2. 즉 어떤 문자 X로 시작하는 길이 N의 사전 순사 전 순 문자열의 종류는 "X" + X로 시작하는 길이 (N-1)의 사전 순 문자열이다.
   1. "a"로 시작하는 길이 2의 사전 순 문자열의 종류는 "a" + "a"로 시작하는 길이 (2-1 = 1)의 사전 순 문자열이다.
   2. "a"+ { "a", "e", "i", "o", "u" }

이 규칙으로 길이 2인 경우도 위의 예시와 비교해보면 적용할 수 있다는 것을 알 수 있다.

 

 그럼 위에서 얻은 점화식을 코드로 그대로 구현하면 해결할 수 있다.