Porównanie ciągów zawierające symbole wieloznaczne

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.

In Porównanie ciągów zawierające symbole wieloznaczne problem, daliśmy dwa ciągi jako drugie ciąg zawiera małe alfabety, a pierwszy zawiera małe alfabety i niektóre wzorce symboli wieloznacznych. 

Wzorce symboli wieloznacznych to:

?: możemy zastąpić ten symbol wieloznaczny dowolnym małym alfabetem.

*: możemy zastąpić ten symbol wieloznaczny dowolnym ciągiem znaków. Dozwolony jest również pusty ciąg.

Sprawdź, czy pierwszy ciąg można przekształcić w drugi ciąg, zastępując wzorce symboli wieloznacznych.

Przykład

Wkład

xy * y?

xyyyxyx

Wydajność

Prawdziwy

Wyjaśnienie

jeśli * zostanie zastąpione przez yyx i? jest zastępowane przez x, wtedy oba ciągi stają się takie same.

Rekurencyjne podejście do porównywania ciągów zawierających symbole wieloznaczne

Case 1: Jeśli znak w pierwszym ciągu jest alfabetem.

Jeśli alfabety w obu ciągach są zgodne, sprawdzamy następny znak w obu ciągach, w przeciwnym razie zwracamy fałsz.

Case 2: Jeśli znak w pierwszym ciągu to „?”.

Możemy wymienić? ze znakiem w drugim ciągu. Więc sprawdzamy następny znak w obu łańcuchach.

Case 3: Jeśli znak w pierwszym ciągu to „*”.

Możemy uznać to za pusty ciąg. Sprawdzamy więc następny znak pierwszego ciągu i aktualny znak drugiego ciągu.

OR

Możemy uznać to za ciąg zawierający znaki podobne do drugiego ciągu. Sprawdź więc aktualny znak pierwszego łańcucha i następny znak drugiego ciągu.

Realizacja

Kod C ++

#include <stdio.h> 
#include <stdbool.h> 
bool match(char *first, char * second) 
{ 
  if (*first == '\0' && *second == '\0') 
    return true; 
  if (*first == '*' && *(first+1) != '\0' && *second == '\0') 
    return false; 
  if (*first == '?' || *first == *second) 
    return match(first+1, second+1); 
  if (*first == '*') 
    return match(first+1, second) || match(first, second+1); 
  return false; 
} 
void test(char *first, char *second) 
{ match(first, second)? puts("Yes"): puts("No"); } 
int main() 
{ 
  test("xy*y?", "xyyyxyx"); 
  return 0; 
} 

Yes

Kod Java

class Check
{ 
static boolean match(String first, String second) 
{ 
  if (first.length() == 0 && second.length() == 0) 
    return true; 
  if (first.length() > 1 && first.charAt(0) == '*' && 
              second.length() == 0) 
    return false; 
  if ((first.length() > 1 && first.charAt(0) == '?') || 
    (first.length() != 0 && second.length() != 0 && 
    first.charAt(0) == second.charAt(0))) 
    return match(first.substring(1), 
          second.substring(1)); 
  if (first.length() > 0 && first.charAt(0) == '*') 
    return match(first.substring(1), second) || 
      match(first, second.substring(1)); 
  return false; 
} 
static void test(String first, String second) 
{ 
  if (match(first, second)) 
    System.out.println("Yes"); 
  else
    System.out.println("No"); 
} 
public static void main(String[] args) 
{ 
  test("xy*y?", "xyyyxyx"); 
  
}

Yes

Dynamiczne podejście do programowania do porównywania ciągów zawierających symbole wieloznaczne

Podejście rekurencyjne sprawdzi wszystkie możliwe przypadki. Tutaj podproblem wielokrotnie wywołuje rozwiązany podproblem. Aby uniknąć ponownego obliczenia tego samego podproblemu, którego użyjemy Programowanie dynamiczne. Zapamiętamy wynik podproblemu po jego obliczeniu i użyjemy go bezpośrednio, gdy będziemy musieli go ponownie obliczyć. Złożoność czasowa Programowanie dynamiczne podejście jest O (n * m).

Realizacja

Kod C ++

#include <bits/stdc++.h> 
using namespace std; 
bool strmatch(char str[], char pattern[], 
      int n, int m) 
{ 

  if (m == 0) 
    return (n == 0); 
  bool lookup[n + 1][m + 1]; 
  memset(lookup, false, sizeof(lookup)); 
  lookup[0][0] = true; 
  for (int j = 1; j <= m; j++) 
    if (pattern[j - 1] == '*') 
      lookup[0][j] = lookup[0][j - 1]; 
  for (int i = 1; i <= n; i++) 
  { 
    for (int j = 1; j <= m; j++) 
    { 
      if (pattern[j - 1] == '*') 
        lookup[i][j] = lookup[i][j - 1] || 
              lookup[i - 1][j]; 
      else if (pattern[j - 1] == '?' || 
          str[i - 1] == pattern[j - 1]) 
        lookup[i][j] = lookup[i - 1][j - 1]; 
      else lookup[i][j] = false; 
    } 
  } 
  return lookup[n][m]; 
} 
int main() 
{ 
  char str[] = "xyyyxyx"; 
  char pattern[] = "xy*y?"; 
  if (strmatch(str, pattern, strlen(str), 
            strlen(pattern))) 
    cout << "Yes" << endl; 
  else
    cout << "No" << endl; 
  return 0; 
} 

Yes

Kod Java

import java.util.Arrays; 
public class check{   
  static boolean strmatch(String str, String pattern, 
                int n, int m) 
  { 
    if (m == 0) 
      return (n == 0); 
    boolean[][] lookup = new boolean[n + 1][m + 1]; 
    for(int i = 0; i < n + 1; i++) 
      Arrays.fill(lookup[i], false); 
    lookup[0][0] = true; 
    for (int j = 1; j <= m; j++) 
      if (pattern.charAt(j - 1) == '*') 
        lookup[0][j] = lookup[0][j - 1]; 
    for (int i = 1; i <= n; i++) 
    { 
      for (int j = 1; j <= m; j++) 
      { 
        if (pattern.charAt(j - 1) == '*') 
          lookup[i][j] = lookup[i][j - 1] || 
                lookup[i - 1][j]; 
        else if (pattern.charAt(j - 1) == '?' || 
          str.charAt(i - 1) == pattern.charAt(j - 1)) 
          lookup[i][j] = lookup[i - 1][j - 1]; 
        else lookup[i][j] = false; 
      } 
    } 
  
    return lookup[n][m]; 
  } 
  
  public static void main(String args[]) 
  { 
    String str = "xyyyxyx"; 
    String pattern = "xy*y?"; 
    if (strmatch(str, pattern, str.length(), 
              pattern.length())) 
      System.out.println("Yes"); 
    else
      System.out.println("No"); 
  
  } 
} 

Yes

Analiza złożoności

Złożoność czasowa: O (mxn)  gdzie n i m to rozmiary obu strun.

Złożoność przestrzeni: O (mxn) gdzie n i m to rozmiary obu strun.

Referencje