정규식 일치

난이도 하드
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 Coursera 이베이 Facebook 골드만 삭스 구글 Microsoft
역 추적 동적 프로그래밍 조회수 81

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

. 정규식 일치 문제는 우리가 두 개의 문자열을 하나 ( x)는 소문자 알파벳과 초로 만 구성됩니다. y)는 "."와 같이 두 개의 특수 문자가있는 소문자 알파벳으로 구성됩니다. 및 "*". 작업은 두 번째 문자열이 첫 번째 문자열과 일치하는지 확인하는 것입니다. 또는 아닙니다. 일치하면 인쇄 "진실" 그렇지 않으면 인쇄 "그릇된".

여기에 사용 된 두 문자는 다음을 의미합니다.

"." – 패턴은 단일 문자, 즉 "."과 일치합니다. 첫 번째 문자열과 일치하는 데 필요한 모든 문자로 바꿀 수 있습니다.

"*"– 패턴은 "*"앞의 0 개 이상의 문자 발생과 일치합니다. 즉, "*"는 첫 번째 문자열과 일치하는 데 필요한만큼 선행 문자로 XNUMX 회 이상 대체 될 수 있습니다.

참고 :

  • x는 비어 있거나 소문자 만 포함 할 수 있습니다.
  • y는 비어 있거나 소문자 만 포함하거나 "."와 같은 문자 만 포함 할 수도 있습니다. 또는 "*"또는 둘 다 (예 : 소문자 및 "."및 "*"와 같은 문자)

입력

x =“aa”

y =“a”

산출

그릇된

설명

y는 전체 문자열과 일치하지 않으므로 "a"(y)는 문자열 "aa"(x)와 일치하지 않습니다.

입력

x =“aa”

y =“a *”

산출

참된

설명

"*"는 선행 문자를 XNUMX 회 이상 반복하고 특수 문자를 제거하는 것을 의미합니다. 따라서 문자열 "a *"에서 "a"를 반복하면 "aa"가되고 두 ​​문자열이 동일 해집니다.

입력

x =“acb”

y = "ab"

산출

참된

설명

여기에서 "."를 바꿀 수 있습니다. 임의의 문자로 "." "ab"by "c"에서 우리는 원하는 문자열 즉, acb를 얻을 것이고, 두 문자열 모두 참이 될 것입니다.

입력

x =“ab”

y =“. *”

산출

참된

설명

". *"는 "모든 문자 (.) 중 XNUMX 개 이상 (*)"를 의미합니다.

암호알고리즘

이 문제에 대한 많은 해결책이 있지만 가장 효율적인 방법은 동적 프로그래밍.

  1. 둘 다의 길이를 얻으십시오 "X""와이" 어떤 변수에서 말한다 "엠""엔" 각각.
  2. 확인하다 "엠" 같음 "0" 그런 다음 인쇄를 반환 그릇된.
  3. 길이가 다음과 같은 2D 배열 (예 : DP)을 초기화합니다. "X" 행과 "와이" 열로.
  4. 마크 정렬 거짓으로.
  5. 초기화 "0,0" 배열의 인덱스 참된
  6. for 루프 실행 "엠" 1에서
    1. for 루프 검사 내부, y [i-1] == '*'인 경우
      1. 그렇다면 dp [0] [i] = dp [0] [j-1]
  7. 중첩 된 for 루프를 초기화합니다. "엠" 두 번째는 1 ~ "엔"
    1. for 루프 검사에서 y [j-1] == '*'인 경우
      1. 그렇다면 dp [i] [j] = dp [i] [j – 1] || dp [i – 1] [j]
    2. 그렇지 않으면 y [j – 1] == '.' || x [i – 1] == y [j – 1]
      1. 그렇다면 dp [i] [j] = dp [i – 1] [j – 1]
    3. 그렇지 않으면 dp [i] [j]를 false로 표시합니다. 즉, dp [i] [j] == false
  8. dp [n] [m]의 결과를 인쇄합니다. 즉, dp의 마지막 색인입니다.

 정규식 일치를위한 C ++ 구현

#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

정규식 일치를위한 Java 구현

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

정규식 매칭을위한 복잡성 분석

시간 복잡성

O (m × n) 여기서 m 길이입니다 "X"n 길이입니다 "와이"

공간 복잡성

O (m × n) 여기서 m 길이입니다 "X"n 길이입니다 "와이"

참조

균열 시스템 설계 인터뷰
Translate »