c - エンコードされたメッセージが与えられたら、それをデコードできる方法の数を数えます

Question

数字のみを含むエンコードされたメッセージが表示されます。次のマッピングも提供されます

 A : 1
 B : 2
 C : 3
 ..
 Z : 26

エンコードされたメッセージが与えられたら、それをデコードできる方法の数を数えます。

例：12（A、B）と（L）の2つの方法でデコードできます

数字を文字列の文字として受け入れ、その各桁をチェックするアルゴリズムを思いつきました。

1.If the first digit of the string array is zero , return zero.

2.for each of its digit(i) from 1 to n perform:

   if str[i-1]>2 || (str[i-1]=='2' && str[i]>'6')
      return 0;

   if(str[i]==0)
      return 0;

メッセージの最初の数字を文字にエンコードしようとするたびに、または可能であれば最初の2桁を文字にエンコードすることができます。単一の「0」に遭遇したり、「32」に遭遇したりするようにエンコードする方法がない場合は、単に戻ります。

この問題はより効率的に解決できますか？

Answer 1

問題に対する現在の近似は正しいです。ただし、明確でないすべてのケースを処理していることに本当に注意する必要があります。これにより、私の答えが必要以上に長くなります。

この問題を確認する正しい方法は、動的計画法の観点からです。message入力文字列をとして、その長さをとして考えてみましょうn。

messageの文字をデコードするには、文字と使用文字を使用してnデコードできる方法がいくつあるかを知る必要があります。あれは、messagen - 1messagen - 2

キャラクターのメッセージn。

                                              1
          1   2   3   4   5   6   7   8   9   0   1
        +---+---+---+---+---+---+---+---+---+---+---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | 1 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+

1桁の長さmessageのn - 1文字を使用します。

                                              1
          1   2   3   4   5   6   7   8   9   0       1
        +---+---+---+---+---+---+---+---+---+---+   +---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | 1 | + | 2 |
        +---+---+---+---+---+---+---+---+---+---+   +---+

2桁の長さmessageのn - 2文字を使用します。

                                                  1
          1   2   3   4   5   6   7   8   9       0   1
        +---+---+---+---+---+---+---+---+---+   +---+---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | + | 1 | 2 |
        +---+---+---+---+---+---+---+---+---+   +---+---+

今、あなたは自分自身に尋ねることができます：

文字と文字をmessageデコードできる方法をいくつ計算するにはどうすればよいですか？n - 1n - 2

それは実際には同じ方法です。最終的には、それを基本ケースに減らします。

文字をways[n]デコードできる方法の数を考えてみましょう。次に、このように置くことができます、messagenways[n]

ways[n] = ways[n - 1] + ways[n - 2]

（空の文字列のウェイの数をどのように定義するかについての手がかりがないため、私はそれを考慮しました1。）

適切な制約と基本ケースを使用して、

• n = 0、

   ways[n] =  1
  

• n > 1とmessage[n]有効でありmessage[n - 1:n]、有効です、

   ways[n] = ways[n - 1] + ways[n - 2]
  

• n > 1message[n]有効であり、message[n - 1:n]無効です。

   ways[n] = ways[n - 1]
  

• n > 1有効ではmessage[n]なく、message[n - 1:n]有効です。

   ways[n] = ways[n - 2]
  

• そうでなければ、

   ways[n] = 0
  

Cの反復decode関数は、次のようになります。

int decode(char* message, size_t len) {
    int i, w, ways[] = { 1, 0 };
    for(i = 0, w; i < len; ++i) {
        w = 0;
        if((i > 0) && ((message[i - 1] == '1') || (message[i - 1] == '2' && message[i] < '7'))) {
            w += ways[1];
        }
        if(message[i] > '0') {
            w += ways[0];
        }
        ways[1] = ways[0];
        ways[0] = w;
    }
    return ways[0];
}

ここideoneで見ることができます。計算に一定の追加メモリを使用しています。

Answer 2

動的計画法ソリューションがどのように機能するかを正確に理解するのに少し時間がかかったので、コメントしたpythonコードで@Alexanderの投稿を補足すると思いました。これがフィボナッチ関数のコーディングにどれほど似ているかを理解することは有用だと思います。また、完全なコード、テスト、実行時の比較を素朴な再帰とgithubにアップロードしました。

def number_of_decodings_fast(code):
    """ Dynamic programming implementation which runs in 
    O(n) time and O(1) space. 
    The implementation is very similar to the dynamic programming
    solution for the Fibonacci series. """
    length = len(code)
    if (length <= 1):
        # assume all such codes are unambiguously decodable
        return 1
    else:
        n_prev = 1 # len 0
        n_current = 1 # len 1
        for i in range(1,length):
            if (
                # a '1' is ambiguous if followed by
                # a digit X=[1-9] since it could be
                # decoded as '1X' or '1'+'X'
                code[i-1]=='1' and 
                code[1] in [str(k) for k in (range(1,10))]
            ) or (
                # a '2' is ambiguous if followed by 
                # a digit X=[1-6] since it could be
                # decoded as '2X' or '2'+'X'
                code[i-1]=='2' and 
                code[i] in [str(k) for k in range(1,7)]
            ):
                # New number of decodings is the sum of
                # decodings obtainable from the code two digits back
                # (code[0:(i-2)] + '[1-2]X' interpretation)
                # and decodings obtainable from the code one digit back
                # (code[0:(i-1)] + 'X' interpretation).
                n_new = n_prev + n_current
            else:
                # New number of decodings is the same as
                # that obtainable from the code one digit back
                # (code[0:(i-1)] + 'X' interpretation).
                n_new = n_current
            # update n_prev and n_current
            n_prev = n_current
            n_current = n_new
        return n_current

Answer 3

再帰的ソリューション

int countdecodes(char * s)
{
    int r = 0;
    switch(*s)
    {
        case 0:
            return 1;
        case '0':
            return 0;
        case '1':
            r = countdecodes(s+1);
            if(*(s+1))
                r = r + countdecodes(s+2);
            return r;
        case '2':
            r = countdecodes(s+1);
            switch(*(s+1))
            {
                case '0': case '1': case '2':
                case '3': case '4': case '5':
                case '6':
                    r = r + countdecodes(s+2);
                default:
                    return r;
            }
        case '3': case '4': case '5': case '6':
        case '7':case '8': case '9':
            return countdecodes(s+1);
        default:
            return 0;
    }
}

サンプルリターン

1. countdecodes（ "123"）; //3を返します
2. countdecodes（ "1230"）; //0を返します
3. countdecodes（ "1220"）; //2を返します
4. countdecodes（ "12321"）; //6を返します

Answer 4

def nombre_codage(message):
    map=[]
    for i in range(1,27,1):
        map.append(i)
    nbr=1
    n=len(message)
    pair_couple=0
    for j in range (0,n,2):
        if int(message[j:j+2]) in map and len(message[j:j+2])==2:
            pair_couple+=1
    nbr+=2**pair_couple-1 
    impair_couple=0
    for k in range (1,n,2):
        if int(message[k:k+2]) in map and len(message[k:k+2])==2:
            impair_couple+=1
    nbr+=2**impair_couple-1    
    return nbr 

これがPythonの解決策です。メッセージを文字列として受け取り、エンコード可能な2つの数値の桁をカウントし、二項係数を使用します。別の形式を使用しまし(C(n-p)=2^n)た。メッセージをエンコードする方法の数をカウントします。

Answer 5

これは、動的計画法を使用した、問題に対する小さくて単純なO（n）ソリューションです。

int ways(string s){
    int n = s.size();
    vector<int> v(n + 1, 1);
    v[n - 1] = s[n - 1] != '0';
    for(int i = n - 2; i >= 0; i--){
        if(s[i] == '0') {v[i] = v[i + 1]; continue;}
        if(s[i] <= '2' && s[i + 1] <= '6') 
            if(s[i + 1] != '0') v[i] = v[i + 1] + v[i + 2];
            else v[i] = v[i + 2];
        else v[i] = v[i + 1];
    }
    return v[0];
}

アイデアは、インデックスごとに歩くことです。そのインデックス（次のインデックスに付加されている）に26以下の数が含まれ、ゼロが含まれていない場合、2つの可能性に分けられます。それ以外の場合は、1つだけです。

ways("123");    //output: 3
ways("1230");   //output: 0
ways("1220");   //output: 2
ways("12321");  //output: 6

Answer 6

私は、O（N）時間計算量とO（1）空間計算量を持つこの問題の単純なパターンベースのソリューションを持っています。

説明例：-

12312

                              1 
                     /                 \
                  1,2                   12
                /     \                   \
            1,2,3      1,23                12,3 
            |             |                    \
        1,2,3,1           1,23,1                12,3,1
        /    \           /       \             /       \
1,2,3,1,2   1,2,3,12   1,23,1,2   1,23,12   12,3,1,2   12,3,12


P1 P2 N  T
1  0  1  1
1  1  2  2
2  1  2  3
3  0  1  3
3  3  2  6

P1は、新しい要素が2桁の数字を形成していないケースの数を表します

P2は、新しい要素が2桁の数字を形成するケースの数を表します

N = 1はp1に関連するケースを表し、N=2はp2に関連するケースを表します

したがって、ケース1と2に関する新しいツリーは次のようになります。

           1
       /       \
      1         2
   /     \       \
  1       2       1
  |       |       |
  1       1       1
 / \     / \     / \
1   2   1   2   1   2

#include <iostream>
#include <string>
using namespace std;


int decode(string s)
{
    int l=s.length();
    int p1=1;
    int p2=0;
    int n;
    int temp;
    for(int i=0;i<l-1;i++)
    {
        if(((int(s[i]-'0')*10)+int(s[i+1]-'0'))<=26)
        {
            n=2;
        }
        else
        {
            n=1;
        }
        temp=p2;
        p2=(n==2)?p1:0;
        p1=p1+t;
    }
    return p1+p2;
}

int main() {
    string s;
    getline(cin,s);
    cout<<decode(s);
    return 0;
}

1から9までの文字にのみ有効です。

Answer 7

再帰的ソリューション

list = []
def findCombiation(s,ls):
    if len(s) == 0:
        list.append(ls)
    ls = ls + "0"
    if s[0:1] == "0":
        findCombiation(s[1:],ls)
    else:
        st = s[:2]
        if st == "":
            return 
        if int(st) > 25 :
            findCombiation(s[1:],ls)
            ls = ls + s[:1]
        else:
            findCombiation(s[1:],ls+s[:1])
            findCombiation(s[2:],ls+s[:2])

findCombiation("99","") 
print(set(list))