Long and not elegant but easy to understand solution


  • 0
    C

    Run time should be O(n), but cannot pass the OJ with TLE. Will give the right answers.
    '''
    public int checkRecord(int n) {

        if(n == 0)return 0;
        if(n == 1)return 3;
        if(n == 2)return 8;
        Map<String,Map<String,Long>> map = new HashMap<>();
        Map<String,Long> NoA  = new HashMap<>();
        NoA.put("pp", 1l);NoA.put("pl", 1l);NoA.put("lp",1l);NoA.put("ll", 1l);
        Map<String, Long> A = new HashMap<>();
        A.put("pp", 0l);A.put("pl", 0l);A.put("lp",0l);A.put("ll", 0l);
        A.put("ap", 1l);A.put("pa", 1l);A.put("la",1l);A.put("al", 1l);
        map.put("A", A);map.put("N", NoA);
        for(long i = 2; i < n;i++){
        	Map<String,Long> tmpA = map.get("A");
        	Map<String,Long> tmpN = map.get("N");
        	long App = tmpA.get("pp") + tmpA.get("lp") + tmpA.get("ap");
        	long Npp = tmpN.get("pp") + tmpN.get("lp");
        	long Apl = tmpA.get("pp") + tmpA.get("lp") + tmpA.get("ap");
        	long Npl = tmpN.get("pp") + tmpN.get("lp");
        	long Alp = tmpA.get("pl") + tmpA.get("ll") + tmpA.get("al");
        	long Nlp = tmpN.get("pl") + tmpN.get("ll");
        	long All = tmpA.get("pl") + tmpA.get("al");
        	long Nll = tmpN.get("pl");
        	long Aap = tmpA.get("pa") + tmpA.get("la");
        	long Apa  = tmpN.get("pp") + tmpN.get("lp");
        	long Ala = tmpN.get("pl") + tmpN.get("ll");
        	long Aal = tmpA.get("pa") + tmpA.get("la");
        	
        	tmpA.put("pp", App%1000000007);tmpA.put("pl", Apl%1000000007);tmpA.put("lp",Alp%1000000007);tmpA.put("ll", All%1000000007);
        	tmpA.put("ap", Aap%1000000007);tmpA.put("pa", Apa%1000000007);tmpA.put("la",Ala%1000000007);tmpA.put("al", Aal%1000000007);
        	tmpN.put("pp", Npp%1000000007);tmpN.put("pl", Npl%1000000007);tmpN.put("lp",Nlp%1000000007);tmpN.put("ll", Nll%1000000007);
        	map.put("A", tmpA);
        	map.put("N", tmpN);	
        }
        long ans = 0;
    	Map<String,Long> tmpA = map.get("A");
    	Map<String,Long> tmpN = map.get("N");
    	for(String str : tmpA.keySet()){
    		ans += tmpA.get(str);
    	}
    	for(String str : tmpN.keySet()){
    		ans += tmpN.get(str);
    	}
    	System.out.println(ans);
    	return (int) (ans%1000000007);
    

    }
    '''


Log in to reply
 

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