LeetCode - 1641. Count Sorted Vowel Strings

 

🔗 1641. Count Sorted Vowel Strings

엄... 처음에 최대한 빨리 끝내고 싶어서 itertools의 product를 사용한 다음에 조건에 안맞는 것들을 없애려고 했는데

product가 n이 33만 되어도 굉~장히 느렸다. 그래서 시간초과..

 

두번째로 생각한 방법은

뒤에서 부터 하나씩 정해서 그 다음 앞에 것은 뒤에것보다 작은(vowel 배열에서 앞에 위치한) 글자여야 한다는 것이다.

사실 vowel도 귀찮아서 걍 [0, 1, 2, 3, 4] 로 했다.

그랬더니 통과했다. 속도는 느려도 메모리는 경쟁력 있었다. 아마 속도는 memorization을 써야하지 않나.. 싶다.

class Solution:
    def __init__(self):
        self.answer = None

    def countVowelStrings(self, n: int):
        self.answer = 0
        vowels = list(range(5))

        def make_list(last_word, count):
            if count == 0:
                self.answer += 1
                return
            for i in range(last_word + 1):
                make_list(i, count - 1)

        for vowel in vowels:
            make_list(vowel, n - 1)
        return self.answer