Share my thinking process - Finite State Machine


  • 1
    Z

    A rewardable sequence can only have 6 states :
    Either has Absence in previous sequence, we define it as hasA[i], or Not Absence, we define it as withoutA[i].
    By each case, we can only have 0, 1, 2 continuous Late at the end of sequence.
    By defining this 6 states, now we can draw all possible transitions. Each time we have 3 options, P, L, or A. The transition relationship is shown as following figure. Notice each time we take a P or A, we immediately end our L continuous record and go back to hasA[0] or withoutA[0].

    Now the implementation is simply the translation of the figure. I attached both my first O(n) space version and the second optimized O(1) space version by observing that the current state only depends on last moment.

    The time complexity is O(n).

    0_1492316033457_fsm_lc552.jpeg

    public class Solution {
    
        public int checkRecord(int n) {
            long M = 1000000007;
            // with i L at the end (i = 0, 1, 2)
            long[][] hasA = new long[3][2];
            long[][] withoutA = new long[3][2];
            
            hasA[0][0] = 1; // 'A'
            withoutA[0][0] = 1; // 'P'
            withoutA[1][0] = 1; // 'L'
            for (int i = 2; i <= n; i++) {
                // only possible with 'P'
                withoutA[0][(i + 1) % 2] = (withoutA[0][i % 2] + withoutA[1][i % 2] + withoutA[2][i % 2]) % M;
                for (int j = 1; j <= 2; j++) {
                    // possible with 'L'
                    withoutA[j][(i + 1) % 2] = withoutA[j - 1][i % 2];
                }
                // possible with 'A' or 'P'
                hasA[0][(i + 1) % 2] = (withoutA[0][(i + 1) % 2] + hasA[0][i % 2] + hasA[1][i % 2] + hasA[2][i % 2]) % M;
                for (int j = 1; j <= 2; j++) {
                    // possible with 'L'
                    hasA[j][(i + 1) % 2] = hasA[j - 1][i % 2];
                }            
            }
            
            long res = 0;
            for (int k = 0; k < 3; k++) {
                res = (res + hasA[k][(n + 1) % 2] + withoutA[k][(n + 1) % 2]) % M;
            }
            return (int) res;
        }    
        
        public int checkRecord2(int n) {
            if (n == 1) return 3;
            // with i L at the end (i = 0, 1, 2)
            int[][] hasA = new int[3][n + 1];
            int[][] withoutA = new int[3][n + 1];
            
            hasA[0][1] = 1; // 'A'
            withoutA[0][1] = 1; // 'P'
            withoutA[1][1] = 1; // 'L'
            for (int i = 2; i <= n; i++) {
                // only possible with 'P'
                withoutA[0][i] = withoutA[0][i - 1] + withoutA[1][i - 1] + withoutA[2][i - 1];
                for (int j = 1; j <= 2; j++) {
                    // possible with 'L'
                    withoutA[j][i] = withoutA[j - 1][i - 1];
                }
                // possible with 'A' or 'P'
                hasA[0][i] = withoutA[0][i - 1] + withoutA[1][i - 1] + withoutA[2][i - 1] + hasA[0][i - 1] + hasA[1][i - 1] + hasA[2][i - 1];
                for (int j = 1; j <= 2; j++) {
                    // possible with 'L'
                    hasA[j][i] = hasA[j - 1][i - 1];
                }            
            }
            
            int res = 0;
            for (int k = 0; k < 3; k++) {
                res += hasA[k][n] + withoutA[k][n];
            }
            return res;
        }
    }
    

Log in to reply
 

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