패턴과 str이라는 문자열이 있다고 가정하고 str이 동일한 패턴을 따르는지 여부를 확인해야 합니다. 여기에서 패턴 팔로우는 패턴의 문자와 str의 비어 있지 않은 부분 문자열 사이에 전단사가 있는 전체 일치를 의미합니다.
따라서 입력이 패턴이 "abaa"이고 str이 "오렌지그린오렌지오렌지"인 경우 출력은 true가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve() 함수를 정의하면 i, j, ptr, s, map m, used라고 하는 하나의 집합이 필요합니다.
-
i>=s의 크기 및 j>=ptr의 크기인 경우 -
-
true를 반환
-
-
i>=s의 크기 또는 j>=ptr의 크기인 경우 -
-
거짓을 반환
-
-
ptr[j]가 m이면 -
-
요청 :=m[ptr[j]]
-
len :=요청 크기
-
len> 크기가 s이면 -
-
거짓을 반환
-
-
인덱스(i에서 len-1까지)에서 s의 부분 문자열이 req 및 solve(i + len, j + 1, ptr, s, m, used)와 같으면 -
-
true를 반환
-
-
거짓을 반환
-
-
그렇지 않으면
-
x :=ptr[j]
-
초기화 k :=i의 경우 k
-
temp :=인덱스에서 s의 부분 문자열(i에서 k - i까지)
-
temp가 사용 중인 경우 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
m[x] :=온도
-
사용된 템에 삽입
-
해결(k + 1, j + 1, ptr, s, m, 사용됨)인 경우 -
-
true를 반환
-
-
m에서 x 삭제
-
사용된 온도에서 삭제
-
-
-
거짓을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
하나의 맵 정의
-
사용된 한 세트 정의
-
반환 해결(0, 0, ptr, s, m, 사용됨)
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(int i, int j, string ptr, string s, map <char, string>& m, set<string>& used){
if (i >= s.size() && j >= ptr.size()) {
return true;
}
if (i >= s.size() || j >= ptr.size())
return false;
if (m.count(ptr[j])) {
string req = m[ptr[j]];
int len = req.size();
if (len > s.size() - i)
return false;
if ((s.substr(i, len) == req) && solve(i + len, j + 1, ptr, s, m, used))
return true;
return false;
}
else {
char x = ptr[j];
for (int k = i; k < s.size(); k++) {
string temp = s.substr(i, k - i + 1);
;
if (used.count(temp))
continue;
m[x] = temp;
used.insert(temp);
if (solve(k + 1, j + 1, ptr, s, m, used))
return true;
m.erase(x);
used.erase(temp);
}
}
return false;
}
bool wordPatternMatch(string ptr, string s) {
map<char, string> m;
set<string> used;
return solve(0, 0, ptr, s, m, used);
}
};
main(){
Solution ob;
cout << (ob.wordPatternMatch("abaa", "orangegreenorangeorange"));
} 입력
"abaa" "orangegreenorangeorange"
출력
1