Dopasowanie wyrażeń regularnych

Poziom trudności Ciężko
Często zadawane pytania Adobe Amazonka Apple Bloomberg Coursera eBay Facebook Goldman Sachs Google Microsoft
Cofanie Programowanie dynamiczne sznurodwiedzajacy 82

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 Dopasowanie wyrażeń regularnych problem podaliśmy dwa ciągi jeden (załóżmy to x) składa się tylko z małych liter i drugiej (załóżmy to y) składa się z małych liter z dwoma znakami specjalnymi, np. „.” i "*". Zadanie polega na znalezieniu, czy drugi ciąg pasuje do pierwszego ciąg albo nie. Jeśli pasuje, wydrukuj "prawdziwe" w przeciwnym razie drukuj "fałszywe".

Użyte tutaj dwa znaki oznaczają:

„.” - wzorzec dopasowuje dowolny pojedynczy znak, tj. „.” można zastąpić dowolnym znakiem wymaganym do dopasowania pierwszego ciągu

„*” - wzorzec dopasowuje 0 lub więcej wystąpień znaku przed „*”, tj. „*” Można zastąpić dowolnym poprzedzającym znakiem zero lub więcej razy, zgodnie z wymaganiami dopasowania pierwszego ciągu

Uwaga:

  • x może być puste lub może zawierać tylko małe litery.
  • y może być również puste, może zawierać tylko małe litery lub tylko znaki, takie jak „”. lub „*” lub oba (tj. małe litery i znaki, takie jak „.” i „*”)

Przykład

Wkład

x = „aa”

y = „a”

Wydajność

fałszywy

Wyjaśnienie

Ponieważ y nie pasuje do całego ciągu, tj. „A” (y) nie pasuje do ciągu „aa” (x).

Wkład

x = „aa”

y = „a *”

Wydajność

prawdziwy

Wyjaśnienie

Ponieważ „*” oznacza powtórzenie poprzedniej litery zero lub więcej razy i usunięcie znaku specjalnego. Więc powtarzając „a” jedynki w ciągu „a *” stanie się „aa” i obie struny staną się takie same.

Wkład

x = „acb”

y = „ab”

Wydajność

prawdziwy

Wyjaśnienie

Tutaj możemy zastąpić „.” dowolnym znakiem, zastępując więc „.” w „ab” przez „c” otrzymamy żądany ciąg, tj. acb, i oba te znaki staną się prawdziwe.

Wkład

x = „ab”

y = „. *”

Wydajność

prawdziwy

Wyjaśnienie

„. *” Oznacza „zero lub więcej (*) dowolnego znaku (.)”.

Algorytm

Istnieje wiele rozwiązań tego problemu, ale najbardziej efektywnym sposobem jest rozwiązanie go za pomocą Programowanie dynamiczne.

  1. Uzyskaj długość obu "X" i „Y” w jakiejś zmiennej powiedz "M" i „N” odpowiednio.
  2. sprawdź, czy "M" równa "0" następnie zwróć wydruk fałszywy.
  3. Zainicjuj tablicę 2d (powiedzmy dp) o długości "X" jako wiersz i „Y” jako kolumna.
  4. zaznaczyć szyk jako fałszywe.
  5. Inicjalizacja "0,0" indeks tablicy jako prawdziwy
  6. Uruchom pętlę for "M" od 1
    1. Wewnątrz do sprawdzenia pętli, jeśli y [i-1] == '*'
      1. Jeśli tak, to dp [0] [i] = dp [0] [j-1]
  7. Zainicjuj zagnieżdżoną pętlę for: jedną z 1 do "M" a drugi z 1 do „N”
    1. W celu sprawdzenia pętli, jeśli y [j-1] == '*'
      1. jeśli tak, to dp [i] [j] = dp [i] [j - 1] || dp [i - 1] [j]
    2. w przeciwnym razie sprawdź, czy y [j - 1] == '.' || x [i - 1] == y [j - 1]
      1. jeśli tak, to dp [i] [j] = dp [i - 1] [j - 1]
    3. w przeciwnym razie oznacz dp [i] [j] jako fałsz, tj. dp [i] [j] == fałsz
  8. Wydrukuj wynik dp [n] [m], czyli ostatni indeks dp

 Implementacja w C ++ w celu dopasowania wyrażeń regularnych

#include <bits/stdc++.h>
using namespace std;

bool isMatch(char x[], char y[])
{
    int n = strlen(x);
    int m = strlen(y);

    if (m == 0)
        return (n == 0);

    bool dp[n + 1][m + 1];

    memset(dp, false, sizeof(dp));

    dp[0][0] = true;

    for (int i = 1; i <= m; i++)
    {
        if (y[i - 1] == '*')
        {
            dp[0][i] = dp[0][i - 1];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (y[j - 1] == '*')
            {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }

            else if (y[j - 1] == '.' || x[i - 1] == y[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1];
            }

            else
            {
                dp[i][j] = false;
            }
        }
    }

    return dp[n][m];
}

int main()
{
    char x[] = "acb";
    char y[] = "a.b";

    cout<< boolalpha<<(isMatch(x, y));
    return 0;
}
true

Implementacja w języku Java do dopasowywania wyrażeń regularnych

import java.util.Arrays;
public class solution {

  static boolean isMatch(String x, String y) {
    int n = x.length();
    int m = y.length();

    if (m == 0)
      return (n == 0);

    boolean[][] dp = new boolean[n + 1][m + 1];

    for (int i = 0; i<n + 1; i++) {
      Arrays.fill(dp[i], false);
    }

    dp[0][0] = true;

    for (int j = 1; j<= m; j++) {
      if (y.charAt(j - 1) == '*') {
        dp[0][j] = dp[0][j - 1];
      }
    }

    for (int i = 1; i<= n; i++) {
      for (int j = 1; j<= m; j++) {

        if (y.charAt(j - 1) == '*') {
          dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
        } else if (y.charAt(j - 1) == '.' || x.charAt(i - 1) == y.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = false;
        }
      }
    }

    return dp[n][m];
  }

  public static void main(String args[]) {
    String x = "acb";
    String y = "a.b";

    System.out.println((isMatch(x, y)));

  }
}
true

Analiza złożoności pod kątem dopasowania wyrażeń regularnych

Złożoność czasowa

O (m × n) gdzie m to długość "X" i n to długość „Y”

Złożoność przestrzeni

O (m × n) gdzie m to długość "X" i n to długość „Y”

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »