# Divide and Conquer Solution using C++

• 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

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