# leetcode 91. Decode Ways

A message containing letters from `A-Z` is being encoded to numbers using the following mapping:

```'A' -> 1
'B' -> 2
...
'Z' -> 26
```

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message `"12"`, it could be decoded as `"AB"` (1 2) or `"L"` (12).

The number of ways decoding `"12"` is 2.

## 算法设计

• Divide：将序列LIST划分为左右两个子序列LISTL和LISTR。
• Conquer：递归的求解LISTL和LISTR的解码方式。若序列中只有一个数字，返回解码方式为1。
• Merge：将LISTL和LISTR的解码方式数相乘，得到res。再考虑合并处的两个数字，即LISTL的最右数字n1与LISTR的最左数字n2，若n1等于1，n2不为0，则将res加上相应的数；若n1等于2，n2为1~6，则将res加上相应的数；其余情况res不变。将得到的res返回。
```package leetcode;

public class Decode_Ways_91 {

public int numDecodings(String s) {
if(s==null||s.equals("")){
return 0;
}
char[] cs=s.toCharArray();
int[][] memo=new int[cs.length][cs.length];
return helper(cs, 0, cs.length-1, memo);
}

public int helper(char[] cs,int left,int right,int[][] memo){
if(memo[left][right]>0){
return memo[left][right];
}
if(left>right){
return 0;
}
if(left==right){
if(cs[left]=='0'){
return 0;
}
else{
return 1;
}
}
int mid=(left+right)/2;
int leftPart=helper(cs, left, mid, memo);
int rightPart=helper(cs, mid+1, right, memo);
int result=leftPart*rightPart;
char borderLeft=cs[mid];
char borderRight=cs[mid+1];
if(borderLeft=='1'||(borderLeft=='2'&&borderRight>='0'&&borderRight<='6')){
int leftleft=1;
if(left<=mid-1){ //防止出现0*2这种情况，修正为1*2
leftleft=helper(cs, left, mid-1, memo);
}
int rightright=1;
if(mid+2<=right){
rightright=helper(cs, mid+2, right, memo);
}
result+=leftleft*rightright;//相当于leftleft*1*rightright(这里的1就是中间合并得到字母的情况）
}
memo[left][right]=result;
return result;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Decode_Ways_91 d=new Decode_Ways_91();
System.out.println(d.numDecodings("0"));
}

}```

```public int numDecodings(String s) {
if (s.length() == 0){
return 0;
}
int[] t = new int[s.length()+1];
t[0] = 1;

if(s.charAt(0)!='0')  t[1]=1;
for(int i=2; i<=s.length(); i++){
if(isValid(s.substring(i-1,i))){
t[i]+=t[i-1];
}

if(isValid(s.substring(i-2,i))){
t[i]+=t[i-2];
}
}

return t[s.length()];
}

public boolean isValid(String s){
if(s.charAt(0)=='0')
return false;
int value = Integer.parseInt(s);
return value>=1&&value<=26;
}```