시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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 개 이상 (*)"를 의미합니다.
암호알고리즘
이 문제에 대한 많은 해결책이 있지만 가장 효율적인 방법은 동적 프로그래밍.
- 둘 다의 길이를 얻으십시오 "X" 및 "와이" 어떤 변수에서 말한다 "엠" 및 "엔" 각각.
- 확인하다 "엠" 같음 "0" 그런 다음 인쇄를 반환 그릇된.
- 길이가 다음과 같은 2D 배열 (예 : DP)을 초기화합니다. "X" 행과 "와이" 열로.
- 마크 정렬 거짓으로.
- 초기화 "0,0" 배열의 인덱스 참된
- for 루프 실행 "엠" 1에서
- for 루프 검사 내부, y [i-1] == '*'인 경우
- 그렇다면 dp [0] [i] = dp [0] [j-1]
- for 루프 검사 내부, y [i-1] == '*'인 경우
- 중첩 된 for 루프를 초기화합니다. "엠" 두 번째는 1 ~ "엔"
- for 루프 검사에서 y [j-1] == '*'인 경우
- 그렇다면 dp [i] [j] = dp [i] [j – 1] || dp [i – 1] [j]
- 그렇지 않으면 y [j – 1] == '.' || x [i – 1] == y [j – 1]
- 그렇다면 dp [i] [j] = dp [i – 1] [j – 1]
- 그렇지 않으면 dp [i] [j]를 false로 표시합니다. 즉, dp [i] [j] == false
- for 루프 검사에서 y [j-1] == '*'인 경우
- 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 길이입니다 "와이"
