cleanUrl: /posts/count-sorted-vowel-strings-dp-using-2dimensions/

어느정도 실마리를 잡았는데 실마리 잡은 상태로 1시간이 넘어가서 discuss를 보고 풀었다. 문제 난위도는 medium 이지만, 접근이 나름 쉬웠다. 다만 그 접근을 코드로 변경하는데 시간이 많이 쏟아진게 사실이다.

문제

Count Sorted Vowel Strings - LeetCode

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

• examples

접근방법

먼저 나올 수 있는 String 배열을 작성해봤다.

n = 2 이면 다음과 같다

["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]

이것은 (a, e, i, o, u) 두개의 조합이다

$n = 2$

결과는 총 15개가 나온다.

$n = 3$

이와 같이 매칭하여 결과는 총 35개가 나온다 (직접 세어봄)

이렇게 그리다보면 어떠한 규칙성을 발견하는데 그것을 table 로 표시하면 상당히 직관적이다.