Sposoby dekodowania

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W zadaniu Decode Ways daliśmy niepuste ciąg zawierający tylko cyfry, określ całkowitą liczbę sposobów jego zdekodowania za pomocą następującego mapowania:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Przykład

S = „123”

Liczba sposobów dekodowania tego ciągu to 3

Jeśli przyjrzymy się bliżej problemowi, możemy zauważyć, że wszystkie liczby jednocyfrowe oprócz 0 są prawidłowe, ale w przypadku liczby dwucyfrowej prawidłowe są tylko liczby od 10 do 26.

Stąd możemy wywnioskować, że w każdym posiadanym przez nas indeksie dwa kroki:

1. Jeśli i-ty element łańcucha nie jest „0”, to mamy jeden sposób na zdekodowanie łańcucha zaczynającego się od i-tego indeksu przy użyciu odwzorowania:

'A' -> 1

'B' -> 2

….

'I' -> 9

2. Jeśli możemy połączyć i-ty i (i + 1) -ty indeks razem, aby utworzyć prawidłową liczbę przy użyciu następującego odwzorowania:

'J' -> 10

'K' -> 11

….

'Z' -> 26

Następnie mamy jeszcze jeden sposób na zdekodowanie łańcucha zaczynającego się od i-tego indeksu.

Algorytm sposobów dekodowania

Krok 1: Zadeklaruj i zainicjalizuj tablicę 1D o rozmiarze n zerem.

Krok 2: Sprawdź, czy możemy zdekodować łańcuch, który zaczyna się i kończy na (n-1) tym indeksie (przypadek bazowy).

Krok 3: Uruchom pętlę i sprawdź na każdym kroku, czy możemy użyć i-tego elementu indeksu jako jednocyfrowej prawidłowej liczby lub połączyć go z (i + 1) tym elementem indeksu, aby utworzyć prawidłową liczbę dwucyfrową.

1. Jeśli s [i]! = '0', to dp [i] + = dp [i + 1]
2. Jeśli s [i] == '1', to dp [i] + = dp [i + 2]
3. Jeśli s [i] == '2' i s [i + 1] <= '6', to dp [i] + = dp [i + 2]

Krok 4: Zwraca dp [0].

Realizacja

Program w C ++ do dekodowania sposobów

#include<bits/stdc++.h>
using namespace std;
int numDecodings(string s) {
    int n=s.length();
    int dp[n+1];
    memset(dp,0,sizeof(dp));
    dp[n]=1;
    if(s[n-1]!='0'){       //if the last chararcter is not zero then we have one way to decode it
        dp[n-1]=1;
    }
    for(int i=n-2;i>=0;i--){
        if(s[i]!='0'){    
            dp[i]+=dp[i+1];
        }
        if(s[i]=='1'){
            dp[i]+=dp[i+2];
        }
        if(s[i]=='2'){
            if(s[i+1]<='6'){
                dp[i]+=dp[i+2];
            }
        }
    }
    return dp[0];
}
int main(){
    string s="452625";
    cout<<"The number of ways to decode the given string is: "<<numDecodings(s);
}

The number of ways to decode the given string is: 4

Program JAVA do dekodowania

public class Main
{
    public static int numDecodings(String s) {
        int n=s.length();
        int[] dp=new int[n+1];
        dp[n]=1;
        if(s.charAt(n-1)!='0'){       //if the last chararcter is not zero then we have one way to decode it
            dp[n-1]=1;
        }
        for(int i=n-2;i>=0;i--){
            dp[i]=0;
            if(s.charAt(i)!='0'){    
                dp[i]+=dp[i+1];
            }
            if(s.charAt(i)=='1'){
                dp[i]+=dp[i+2];
            }
            if(s.charAt(i)=='2'){
                if(s.charAt(i+1)<='6'){
                    dp[i]+=dp[i+2];
                }
            }
        }
        return dp[0];
    }
  public static void main(String[] args) {
      String s="23572";
    System.out.println("The number of ways to decode the given string is: "+numDecodings(s));
  }
}

The number of ways to decode the given string is: 2

Analiza złożoności sposobów dekodowania

Złożoność czasowa: O (n) gdzie n jest długością podanego ciągu.

Przechodzimy przez dany ciąg tylko raz, stąd złożoność wynosi O (n)

Złożoność przestrzeni: O (n) ponieważ przechowujemy liczbę sposobów na każdym kroku w tablicy dp, co prowadzi nas do złożoności przestrzeni liniowej.

Referencje