1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    private int modulo = 1000000007;
    private Integer[][] memo;
    private Map<Character, Integer> charIndex;

    public int countVowelPermutation(int n) {
        int ans = 0;
        char[] vowels = new char[] { 'a', 'e', 'i', 'o', 'u' };
        memo = new Integer[n][5];
        charIndex = new HashMap<>();
        for (int i = 0; i < vowels.length; i++) {
            charIndex.put(vowels[i], i);
        }
        for (char vowel : vowels) {
            ans = (ans % modulo + helper(n, 0, vowel) % modulo) % modulo;
        }
        return ans % modulo;
    }

    private int helper(int n, int pos, char currChar) {
        int ans = 0, currCharIndex = charIndex.get(currChar);
        if (pos == n - 1) {
            return memo[pos][currCharIndex] = 1;
        }
        if (memo[pos][currCharIndex] != null) {
            return memo[pos][currCharIndex];
        }
        if (currChar == 'a') {
            ans = (ans % modulo + helper(n, pos + 1, 'e') % modulo) % modulo;
        } else if (currChar == 'e') {
            ans = (ans % modulo + helper(n, pos + 1, 'a') % modulo + helper(n, pos + 1, 'i') % modulo) % modulo;
        } else if (currChar == 'i') {
            ans = (ans % modulo + helper(n, pos + 1, 'a') % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 'e') % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 'o') % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 'u') % modulo) % modulo;
        } else if (currChar == 'o') {
            ans = (ans % modulo + helper(n, pos + 1, 'i') % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 'u') % modulo) % modulo;
        } else if (currChar == 'u') {
            ans = (ans % modulo + helper(n, pos + 1, 'a') % modulo) % modulo;
        }
        return memo[pos][currCharIndex] = ans;
    }
}

Recursion + memoization. 比较基础. pos表示我们要算从哪个位置开始及之后的substring的permutation是什么, currChar表示当前位置的char是什么. 这能告诉我们下一个位置可以填什么char.

其实这里的char不一定非要用实际的a, e, i, o, u. 我们可以用数字代替, 这样就不需要map来记录char和index的mapping了. 也就是下面这个解法.

时间复杂度: O(N) 一般这种就是想进行了多少次recursion call. 其实也就是有多少种状态. 那么就看我们的memo大小就完事儿了. memo是5N, 因此是O(N)
空间复杂度: O(N) memo需要存结果.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    private int modulo = 1000000007;
    private Integer[][] memo;
    private Map<Character, Integer> charIndex;

    public int countVowelPermutation(int n) {
        int ans = 0;
        memo = new Integer[n][5];
        for (int i = 0; i < 5; i++) {
            ans = (ans % modulo + helper(n, 0, i) % modulo) % modulo;
        }
        return ans % modulo;
    }

    private int helper(int n, int pos, int currChar) {
        if (memo[pos][currChar] != null) {
            return memo[pos][currChar];
        }
        if (pos == n - 1) {
            return memo[pos][currChar] = 1;
        }
        int ans = 0;
        if (currChar == 0) {
            ans = (ans % modulo + helper(n, pos + 1, 1) % modulo) % modulo;
        } else if (currChar == 1) {
            ans = (ans % modulo + helper(n, pos + 1, 0) % modulo + helper(n, pos + 1, 2) % modulo) % modulo;
        } else if (currChar == 2) {
            ans = (ans % modulo + helper(n, pos + 1, 0) % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 1) % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 3) % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 4) % modulo) % modulo;
        } else if (currChar == 3) {
            ans = (ans % modulo + helper(n, pos + 1, 2) % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 4) % modulo) % modulo;
        } else if (currChar == 4) {
            ans = (ans % modulo + helper(n, pos + 1, 0) % modulo) % modulo;
        }
        return memo[pos][currChar] = ans;
    }
}

上一种解法使用int作为char.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private long modulo = 1000000007;

    public int countVowelPermutation(int n) {
        long ans = 0;
        long[][] dp = new long[n][5];
        for (int i = 0; i < 5; i++) {
            dp[n - 1][i] = 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            dp[i][0] = dp[i + 1][1];
            dp[i][1] = (dp[i + 1][0] + dp[i + 1][2]) % modulo;
            dp[i][2] = (dp[i + 1][0] + dp[i + 1][1] + dp[i + 1][3] + dp[i + 1][4]) % modulo;
            dp[i][3] = (dp[i + 1][2] + dp[i + 1][4]) % modulo;
            dp[i][4] = dp[i + 1][0];
        }
        for (int i = 0; i < 5; i++) {
            ans = (ans + dp[0][i]) % modulo;
        }
        return (int) ans;
    }
}

直接按照recurison的逻辑转dp就容易了. 就看某个状态下(pos以及currChar)的结果需要之后的什么状态下的结果即可. 每一个状态就对应dp中的每个位置.

时间复杂度: O(n)
空间复杂度: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    private long modulo = 1000000007;

    public int countVowelPermutation(int n) {
        long ans = 0;
        long[] dp = new long[5];
        long[] lastRow = new long[5];
        for (int i = 0; i < 5; i++) {
            dp[i] = 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < 5; j++) {
                lastRow[j] = dp[j];
            }
            dp[0] = lastRow[1];
            dp[1] = (lastRow[0] + lastRow[2]) % modulo;
            dp[2] = (lastRow[0] + lastRow[1] + lastRow[3] + lastRow[4]) % modulo;
            dp[3] = (lastRow[2] + lastRow[4]) % modulo;
            dp[4] = lastRow[0];
        }
        for (int i = 0; i < 5; i++) {
            ans = (ans + dp[i]) % modulo;
        }
        return (int) ans;
    }
}

1D dp, 因为我们发现我们只使用前一行的数据. 因此用一个数组存前一行的dp数据即可.
时间复杂度: O(n)
空间复杂度: O(1)