TLE but correct Java recursive solution.


  • 0
    public class Solution {
    public int numWays(int n, int k) {
        if(k==0||n==0)return 0;
        if(n<=2&&k==1){
            return 1;
        }
        if(n==1&&k>=1){
            return k;
        }
        return helper(n,k,1,false,k);
    }
    public int helper(int n,int k,int i, boolean last_two_same, int currproduct){
        if(i<n-1){
            if(last_two_same==true){
                return helper(n,k,i+1,false,(k-1)*currproduct);
            }
            else{
                return helper(n,k,i+1,true,currproduct) + helper(n,k,i+1,false,(k-1)*currproduct);
            }
        }
        else{//i==n-1
            if(last_two_same==true){
                return (k-1)*currproduct;
            }
            else{
                return k*currproduct;
            }
        }
    }
    }
    

    The main idea is similar to using 2d array to store the information. I use a helper function to record if the last 2 posts share the same color and the current product of one condition.


  • 0
    E

    yeah same here, can not pass the last case, so sad. I wonder in real interview do we have to write iterative solution rather than recursion?

    public int numWays(int n, int k) {
            if (n == 1) return k;
            if (k == 0 || n == 0)  return 0;
            //n!=1 or 0 now
            if (k == 1) {
                if (n == 2) return 1;
                else return 0;
            }
            
            int res = k *(helper(true, 1, n - 1, k) + helper(false, 1, n - 1, k));
            return res;
        }
        private int helper(boolean same, int i, int bound, int k) {
            if (i == bound) {
                if (same) return 1;
                else return k - 1; // x = k - 1 
            }
            else {
                if (same) return helper(false, i + 1, bound, k);
                else return (k - 1) * (helper(true, i + 1, bound, k) + helper(false, i + 1, bound, k)); 
            }
        }
    

Log in to reply
 

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