Sposoby dekodowania

Poziom trudności Średni
Często zadawane pytania Adobe Amazonka Cisco Pamięci danych Facebook Goldman Sachs Google JP Morgan Microsoft Morgan Stanley wyrocznia Kwadratowe
Programowanie dynamiczne sznurodwiedzajacy 97

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

Sposoby dekodowania

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

Wywiady dotyczące projektowania systemu pękania
Translate »