資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中的單詞模式 II
假設我們有一個模式和一個稱為 str 的字串，我們需要檢查 str 是否遵循相同的模式。這裡的模式匹配意味著完全匹配，即模式中的字母和 str 中的非空子字串之間存在雙射關係。
因此，如果輸入模式為“abaa”，str 為“orangegreenorangeorange”，則輸出為 true
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 solve()，它將接收 i、j、ptr、s、一個對映 m、一個集合 used 作為引數。
如果 i >= s 的大小 且 j >= ptr 的大小，則：
返回 true
如果 i >= s 的大小 或 j >= ptr 的大小，則：
返回 false
如果 ptr[j] 存在於 m 中，則：
req := m[ptr[j]]
len := req 的大小
如果 len > s 的大小，則：
返回 false
如果 s 從索引 (i 到 len-1) 的子字串與 req 相同且 solve(i + len, j + 1, ptr, s, m, used) 為真，則：
返回 true
返回 false
否則
x := ptr[j]
對於 k 從 i 初始化，當 k < s 的大小時，更新 (k 增加 1)，執行：
temp := s 從索引 (i 到 k - i) 的子字串
如果 temp 存在於 used 中，則：
忽略以下部分，跳到下一次迭代
m[x] := temp
將 temp 插入 used
如果 solve(k + 1, j + 1, ptr, s, m, used) 為真，則：
返回 true
從 m 中刪除 x
從 used 中刪除 temp
返回 false
在主方法中執行以下操作：
定義一個對映 m
定義一個集合 used
返回 solve(0, 0, ptr, s, m, used)
示例
讓我們來看下面的實現，以便更好地理解：
#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
199 次瀏覽
