|
| 1 | +/* Bottom-Up Approach |
| 2 | +----------------------------------------- |
| 3 | + Time Complexity : O(n) |
| 4 | + Space Complexity : O(n) |
| 5 | +----------------------------------------*/ |
| 6 | + |
1 | 7 | classSolution { |
2 | | -// 0: 'a', 1: 'e', 2: 'i', 3: 'o', 4: 'u' |
| 8 | +intMOD = (int)1e9+7; |
3 | 9 |
|
4 | | -privatestaticintMOD =1_000_000_000 +7; |
5 | | - |
6 | | -privateintgetSum(long[]arr) { |
7 | | -longsum =0; |
8 | | -for(longx:arr) { |
9 | | -sum =sum +x; |
10 | | -sum =sum %MOD; |
| 10 | +publicintcountVowelPermutation(intn) { |
| 11 | +if (n ==1) { |
| 12 | +return5; |
11 | 13 | } |
12 | | -return (int)sum; |
13 | | - } |
14 | | - |
15 | | -privatelong[]getBaseCounts() { |
16 | | -returnnewlong[]{1,1,1,1,1}; |
17 | | - } |
18 | | - |
19 | | -privateMap<Integer,List<Integer>>getNextCountMapping() { |
20 | | -Map<Integer,List<Integer>>map =newHashMap<>(); |
21 | | - |
22 | | -/* 0 1 2 3 4 |
23 | | - a e i o u |
24 | | -
|
25 | | - Reverse mapping i.e. "depends on" |
26 | | - {a: [e, i, u]}, {e: [a, i]}, {i: [e, o]}, |
27 | | - {o: [i]}, {u: [i, o]} |
28 | | - */ |
29 | | - |
30 | | -map.put(0,newArrayList<>(List.of(1,2,4))); |
31 | | -map.put(1,newArrayList<>(List.of(0,2))); |
32 | | -map.put(2,newArrayList<>(List.of(1,3))); |
33 | | -map.put(3,newArrayList<>(List.of(2))); |
34 | | -map.put(4,newArrayList<>(List.of(2,3))); |
35 | | - |
36 | | -returnmap; |
37 | | - } |
38 | | - |
39 | | -privatelong[]getNextCounts( |
40 | | -long[]currentCounts, |
41 | | -Map<Integer,List<Integer>>mapNextCounting |
42 | | - ) { |
43 | | -long[]nextCounts =newlong[5]; |
44 | | -Arrays.fill(nextCounts,0); |
45 | | - |
46 | | -// Mapping conversion |
47 | | -for(intkey:mapNextCounting.keySet()) { |
48 | | -for(intval:mapNextCounting.get(key)) { |
49 | | -nextCounts[val] += (long)currentCounts[key]; |
50 | | -nextCounts[val] %=MOD; |
51 | | - } |
| 14 | + |
| 15 | +long[][]dp =newlong[n +1][5]; |
| 16 | +for (intj =0;j <5;j++) { |
| 17 | +dp[1][j] =1; |
52 | 18 | } |
53 | | - |
54 | | -returnnextCounts; |
| 19 | + |
| 20 | +for (inti =2;i <=n;i++) { |
| 21 | +dp[i][0] =dp[i -1][1]; |
| 22 | +dp[i][1] = (dp[i -1][0] +dp[i -1][2]) %MOD; |
| 23 | +dp[i][2] = (dp[i -1][0] +dp[i -1][1] +dp[i -1][3] +dp[i -1][4]) %MOD; |
| 24 | +dp[i][3] = (dp[i -1][2] +dp[i -1][4]) %MOD; |
| 25 | +dp[i][4] =dp[i -1][0]; |
| 26 | + } |
| 27 | + |
| 28 | +longresult =0; |
| 29 | +for (intj =0;j <5;j++) { |
| 30 | +result = (result +dp[n][j]) %MOD; |
| 31 | + } |
| 32 | + |
| 33 | +return (int)result; |
55 | 34 | } |
56 | | - |
| 35 | +} |
| 36 | + |
| 37 | +/* Top Down Approach |
| 38 | +----------------------------------------- |
| 39 | + Time Complexity : O(n) |
| 40 | + Space Complexity : O(n) |
| 41 | +----------------------------------------*/ |
| 42 | + |
| 43 | +classSolution { |
| 44 | +HashMap<String,Integer>memo =newHashMap<>(); |
| 45 | +intMOD = (int)1e9+7; |
| 46 | + |
57 | 47 | publicintcountVowelPermutation(intn) { |
58 | | -long[]counts =getBaseCounts(); |
59 | | -if(n ==1) { |
60 | | -returngetSum(counts); |
61 | | - } |
| 48 | +longans =0; |
| 49 | +ans = (ans +dfs('a',n,1)) %MOD; |
| 50 | +ans = (ans +dfs('e',n,1)) %MOD; |
| 51 | +ans = (ans +dfs('i',n,1)) %MOD; |
| 52 | +ans = (ans +dfs('o',n,1)) %MOD; |
| 53 | +ans = (ans +dfs('u',n,1)) %MOD; |
| 54 | +return (int)ans; |
| 55 | + } |
| 56 | + |
| 57 | +privateintdfs(charc,intn,intl){ |
| 58 | +if(l ==n) |
| 59 | +return1; |
62 | 60 |
|
63 | | -Map<Integer,List<Integer>>mapNextCounting; |
64 | | -mapNextCounting =getNextCountMapping(); |
65 | | - |
66 | | -for(inti=1;i<n;i++) { |
67 | | -counts =getNextCounts(counts,mapNextCounting); |
| 61 | +Stringkey =c +"_" +l; |
| 62 | +if (memo.containsKey(key))returnmemo.get(key); |
| 63 | + |
| 64 | +longres =0; |
| 65 | +if(c =='a') { |
| 66 | +res =dfs('e',n,l+1); |
| 67 | + }elseif(c =='e') { |
| 68 | +res = (res +dfs('a',n,l+1)) %MOD; |
| 69 | +res = (res +dfs('i',n,l+1)) %MOD; |
| 70 | + }elseif(c =='i') { |
| 71 | +res = (res +dfs('a',n,l+1)) %MOD; |
| 72 | +res = (res +dfs('e',n,l+1)) %MOD; |
| 73 | +res = (res +dfs('o',n,l+1)) %MOD; |
| 74 | +res = (res +dfs('u',n,l+1)) %MOD; |
| 75 | + }elseif(c =='o') { |
| 76 | +res = (res +dfs('i',n,l+1)) %MOD; |
| 77 | +res = (res +dfs('u',n,l+1)) %MOD; |
| 78 | + }else { |
| 79 | +res =dfs('a',n,l+1); |
68 | 80 | } |
69 | | - |
70 | | -returngetSum(counts); |
| 81 | + |
| 82 | +memo.put(key, (int)(res %MOD)); |
| 83 | +return (int)(res %MOD); |
71 | 84 | } |
72 | 85 | } |