LeetCode 552: Student Attendance Record II
Problem Description
Explanation
To solve this problem, we can use dynamic programming. We can define two states: the number of days passed n and the number of 'A's encountered aCount. We can also keep track of the number of consecutive 'L's encountered lCount.
We can initialize a 3D array dp where dp[n][aCount][lCount] represents the number of valid attendance records of length n with aCount 'A's and ending with lCount consecutive 'L's.
We can then iterate through the possible states based on the current character being 'P', 'A', or 'L' and update the values in the dp array accordingly.
The final answer will be the sum of all valid attendance records for n days with less than 2 'A's and no more than 2 consecutive 'L's.
Time Complexity
The time complexity of this solution is O(n) where n is the input number of days.
Space Complexity
The space complexity of this solution is O(n) where n is the input number of days.
Solutions
class Solution {
public int checkRecord(int n) {
int mod = 1000000007;
long[][][] dp = new long[n + 1][2][3];
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
// Ending with 'P'
for (int a = 0; a <= 1; a++) {
for (int l = 0; l <= 2; l++) {
dp[i][a][0] = (dp[i][a][0] + dp[i - 1][a][l]) % mod;
}
}
// Ending with 'A'
for (int l = 0; l <= 2; l++) {
dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][l]) % mod;
}
// Ending with 'L'
for (int a = 0; a <= 1; a++) {
for (int l = 1; l <= 2; l++) {
dp[i][a][l] = (dp[i][a][l] + dp[i - 1][a][l - 1]) % mod;
}
}
}
long sum = 0;
for (int a = 0; a <= 1; a++) {
for (int l = 0; l <= 2; l++) {
sum = (sum + dp[n][a][l]) % mod;
}
}
return (int) sum;
}
}Related LeetCode Problems
Loading editor...