当前位置:网站首页>Leetcode 91. Decoding method

Leetcode 91. Decoding method

2021-04-26 11:57:46 ai52learn

One contains letters  A-Z The message is mapped as follows code :

'A' -> 1
'B' -> 2
...
'Z' -> 26
want decode Encoded message , All numbers must be based on the above mapping method , Back to letters ( There may be several ways ). for example ,"11106" It can be mapped to :

"AAJF" , Group messages into (1 1 10 6)
"KJF" , Group messages into (11 10 6)
Be careful , Messages cannot be grouped into   (1 11 06) , because "06" Cannot map to "F" , This is because "6" and "06" It's not equivalent in mapping .

Here's a number only Non empty character string s , Please calculate and return decode Methodical total .

The question data guarantee that the answer is definitely one 32 position The integer of .

Example 1:

Input :s = "12"
Output :2
explain : It can be decoded as "AB"(1 2) perhaps "L"(12).
Example 2:

Input :s = "226"
Output :3
explain : It can be decoded as "BZ" (2 26), "VF" (22 6), perhaps "BBF" (2 2 6) .
Example 3:

Input :s = "0"
Output :0
explain : No characters are mapped to 0 Number at the beginning .
contain 0 The effective mapping of is 'J' -> "10" and 'T'-> "20" .
Because there are no characters , So there is no effective way to decode this , Because all numbers need to be mapped .
Example 4:

Input :s = "06"
Output :0
explain :"06" Can't map to "F" , Because the string contains leading 0("6" and "06" It's not equivalent in mapping ).

Tips :

1 <= s.length <= 100
s Numbers only , And may contain leading zeros .

Solution code

func numDecodings(s string) int {
    n:=len(s)
    d:=make([][2]int,n)
    vis:=make([]int,n)
    for i:=0;i<n;i++{
        if s[i]=='0'{
            vis[i]=-1
            if i-1<0||s[i-1]>'2'||s[i-1]=='0'{
                return 0
            }else{
                vis[i-1]=-1
            }
        }
    }
    d[0][0]=1// Take a 
    d[0][1]=0// Take two. 
    j:=1
    is0:=false
    for i:=1;i<n&&j<n;j++{
        fmt.Println("i: ",vis[i])
        if is0==false&&vis[i]!=-1&&s[i]!='0'&&(s[i-1]=='1'||s[i-1]=='2'&&s[i]<='6'){
            // It can be combined with the front , Or you can be alone 
            d[j][0]=d[j-1][0]+d[j-1][1]
            d[j][1]=d[j-1][0]
        }else{
            d[j][0] = d[j-1][0]+d[j-1][1]
            d[j][1] = 0 // It can't be combined 
        }
        is0=false
        if i<n&&vis[i]==-1{
            is0 = true
        }
        for i++;i<n&&vis[i]==-1;i++{
        }
        
    }
    return d[j-1][0]+d[j-1][1]
}

 

版权声明
本文为[ai52learn]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/04/20210424213247130r.html