Leetcode

Student Attendance Record II

  • Time:O(n)
  • Space:O(1)

C++

class Solution {
 public:
  int checkRecord(int n) {
    constexpr int kMod = 1e9 + 7;
    // dp[i][j] := length so far w/ i A's and the latest chars are j L's
    vector<vector<long>> dp(2, vector<long>(3));
    dp[0][0] = 1;

    while (n--) {
      const auto prev(dp);

      // append P
      dp[0][0] = (prev[0][0] + prev[0][1] + prev[0][2]) % kMod;

      // append L
      dp[0][1] = prev[0][0];

      // append L
      dp[0][2] = prev[0][1];

      // append A or append P
      dp[1][0] = (prev[0][0] + prev[0][1] + prev[0][2] +
                  prev[1][0] + prev[1][1] + prev[1][2]) % kMod;

      // append L
      dp[1][1] = prev[1][0];

      // append L
      dp[1][2] = prev[1][1];
    }

    return accumulate(begin(dp), end(dp), 0, [](int s, vector<long>& row) {
      return (s + accumulate(begin(row), end(row), 0L)) % kMod;
    });
  }
};

JAVA

class Solution {
  public int checkRecord(int n) {
    final int kMod = (int) 1e9 + 7;
    // dp[i][j] := length so far w/ i A's and the latest chars are j L's
    long[][] dp = new long[2][3];
    dp[0][0] = 1;

    while (n-- > 0) {
      long[][] prev = Arrays.stream(dp)
                          .map((long[] A) -> A.clone())
                          .toArray((int length) -> new long[length][]);

      // append P
      dp[0][0] = (prev[0][0] + prev[0][1] + prev[0][2]) % kMod;

      // append L
      dp[0][1] = prev[0][0];

      // append L
      dp[0][2] = prev[0][1];

      // append A or append P
      dp[1][0] = (prev[0][0] + prev[0][1] + prev[0][2] +
                  prev[1][0] + prev[1][1] + prev[1][2]) % kMod;

      // append L
      dp[1][1] = prev[1][0];

      // append L
      dp[1][2] = prev[1][1];
    }

    return (int) ((dp[0][0] + dp[0][1] + dp[0][2] + dp[1][0] + dp[1][1] + dp[1][2]) % kMod);
  }
}

Python

class Solution:
  def checkRecord(self, n: int) -> int:
    kMod = int(1e9) + 7
    # dp[i][j] := length so far w/ i A's and the latest chars are j L's
    dp = [[0] * 3 for _ in range(2)]
    dp[0][0] = 1

    for _ in range(n):
      prev = [A[:] for A in dp]

      # append P
      dp[0][0] = (prev[0][0] + prev[0][1] + prev[0][2]) % kMod

      # append L
      dp[0][1] = prev[0][0]

      # append L
      dp[0][2] = prev[0][1]

      # append A or append P
      dp[1][0] = (prev[0][0] + prev[0][1] + prev[0][2] +
                  prev[1][0] + prev[1][1] + prev[1][2]) % kMod

      # append L
      dp[1][1] = prev[1][0]

      # append L
      dp[1][2] = prev[1][1]

    return (sum(dp[0]) + sum(dp[1])) % kMod