Divide and Conquer Solution using C++


  • 0
    Z

    Here is my code:

    int numDecodings(string s) {
        if(s.empty()){
            return 0;
        }
        return dnc(0, s.length() - 1, s);
    }
    
    int dnc(int start, int end, string& s){
        if(end == start){
            if(s[start] == '0'){
                return 0;
            }
            return 1;
        }
        if(end < start){
            return -1;
        }
        
        if((s[(start + end) / 2] - '0') * 10 + (s[(start + end) / 2 + 1] - '0') <= 26){
            int leftNoMid = dnc(start, (start + end) / 2 - 1, s);
            int rightNoMid = dnc((start + end) / 2 + 2, end, s);
            int total = leftNoMid * rightNoMid;
            
            if(s[(start + end) / 2] == '0'){
                total = 0;
            }
            else{
                if(leftNoMid == -1 && rightNoMid == -1){
                // both leftNoMid part and rightNoMid part don't exist
                    total = 1;
                }
                else{
                    if(leftNoMid == -1){
                    // leftNoMid part doesn't exist
                        total = rightNoMid;
                    }
                    else if(rightNoMid == -1){
                    // rightNoMid part doesn't exist
                        total = leftNoMid;
                    }
                }
            }
            
            return dnc(start, (start + end) / 2, s) * dnc((start + end) / 2 + 1, end, s) + total;
        }
        else{
            return dnc(start, (start + end) / 2, s) * dnc((start + end) / 2 + 1, end, s);
        }
    }
    

    The basic idea is like:

    1. Divide the string into two parts
    2. If the middle two characters can not be decoded (for example, "27"), then the total number of ways decoding string s is the product of left part and right part
    3. Else, the total number of ways decoding string s is (left * right + leftNoMid * rightNoMid), where left means left part and right means right part, leftNoMid means left part without s[(start + end) / 2] and rightNoMid means right part without s[(start + end) / 2 + 1] ( And the return value should be discussed case-by-case. For more details, please check my code)

    Base case:

    If end == start && s[start] == '0', then return 0, which means this part can't be decoded

    If end == start && s[start] != '0', then return 1, which means this part has one way to be decoded

    If end < start, then return -1, which means this part doesn't exist


Log in to reply
 

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