Simple Java O(n) solution


  • 14
    static final int M = 1000000007;
    
    public int checkRecord(int n) {
        long[] PorL = new long[n + 1]; // ending with P or L, no A
        long[] P = new long[n + 1]; // ending with P, no A
        PorL[0] = P[0] = 1; PorL[1] = 2; P[1] = 1;
    
        for (int i = 2; i <= n; i++) {
            P[i] = PorL[i - 1];
            PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M;
        }
        
        long res = PorL[n];
        for (int i = 0; i < n; i++) { // inserting A into (n-1)-length strings
        	long s = (PorL[i] * PorL[n - i - 1]) % M;
            res = (res + s) % M;
        }
        
        return (int) res;
    }
    

  • 0
    T

    Nice solution.
    I was trying to solve this problem in math way. However end up in this DP solution.


  • 1
    Y

    the following is my understanding for your code, if wrong, pls correct me:

    P[i] = PorL[i - 1]; //this line means ending with P, just appending P in PorL
    PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M; //P[i] end with P, P[i-1], end with one L(or PL), P[i-2], end with two L(or LL).

    and last logic ,res init value with PorL without A, and add one A to the sequence.
    long res = PorL[n];
    for (int i = 0; i < n; i++) { // inserting A into (n-1)-length strings
    long s = (PorL[i] * PorL[n - i - 1]) % M;
    res = (res + s) % M;
    }
    very nice and clean solution.


  • 0
    V

    When inserting A into (n-1) length no-A string, can it be simplified to below line?

    res = (res + n * PorL[n-1] ) % M;


  • 0
    S

    @vincexu You cannot use it.
    Because it will miss some situations like ".LLL.", which are correct after inserting an A into it.


  • 0
    S

    A very nice solution!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.