vector<string> decodeWays(const string& a)
{
    vector<string> res;
    size_t n=a.size();
    if(n==0) return res;
    vector<vector<string>> dp(n);
    if(check(a[0]) dp[0].push_back(a[0]-'0'+'a');
    if(n==1) return dp[0];
    if(check(a[0]) && check(a[1])) dp[1].push_back(dp[0].back()+(a[1]-'0'+'a'));
    if(check(a[0], a[1]) {
        int d=(a[0]-'0')*10+(a[1]-'0');
        dp[1].push_back(d+'a');
    }
    for(size_t i=2;i<n;i++) {
         if(check(a[i])) {
             for(auto e : dp[i-1]){
                 dp[i].push_back(e+(a[i]-'0'+'a'));
             }
         }
         if(check(a[i-1], a[i]) {
             int d=(a[i-1]-'0')*10+(a[i]-'0');
             for(auto e : dp[i-2]){
                 dp[i].push_back(e+(d+'a'));
             }
         }
    }
    return dp[n-1];
}

bool check(char one){
    return one!='0';
}

bool check(char one, char two) {
    return one=='1' || (one=='2' && two<='6');
}