파비의 매일매일 공부기록

Today's Challenge 본문

Problem Solving/LeetCode

Today's Challenge

fabichoi 2022. 5. 11. 23:45

https://leetcode.com/problems/count-sorted-vowel-strings/

 

Count Sorted Vowel Strings - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

오늘은 최적화도 좀 해봤다. 원래 27% 빠른 거에서 97%까지 끌어올림.
DP로 모든 case에 대해서 구해도 되긴 하는데.. n=3을 손으로 계산해보니 패턴이 보여서 그냥 수학식으로 해결했다.

class Solution:
    def countVowelStrings(self, n: int) -> int:
        res = [1, 1, 1, 1, 1]
        for i in range(1, n):
            r = sum(res)
            temp = [r, r-res[0], r-res[0]-res[1], r-res[0]-res[1]-res[2], 1]
            res = temp
        return sum(res)
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

Today's Challenge  (0) 2022.05.13
Today's Challenge  (0) 2022.05.12
Today's Challenge  (0) 2022.05.10
Today's Challenge  (0) 2022.05.09
Today's Challenge  (0) 2022.05.08
'Problem Solving/LeetCode' Related Articles more
Comments