C++ 中的同构字符串
c++server side programmingprogramming更新于 2025/6/25 17:07:17
假设有两个字符串 s 和 t;我们需要检查它们是否同构。如果 s 中的字符可以替换为 t，则称这两个字符串同构。
所有出现的字符都必须替换为另一个字符，同时保持字符顺序不变。没有两个字符可以映射到同一个字符，但一个字符可以映射到自身。
因此，如果输入类似于 s = "egg"，t = "add"，则输出将为 true，因为 e 可以映射到 a，而 g 可以映射到 d。
为了解决这个问题，我们将遵循以下步骤 −
定义一个大小为 256 的数组 arr，并用 -1 填充
定义一个大小为 256 的数组 visitor，并用 0 填充
定义一个大小为 256 的数组 visitor1，并用 0 填充
初始化 i := 0，当 i
如果 visitor[s[i]] 等于 1 或 visitor1[t[i]] 等于 1，则 −
如果 arr[s[i]] 不等于 t[i] - 'a' 的 ASCII 码，则 −
返回 false
否则
visited[s[i]] := 1
visited1[t[i]] := 1
arr[s[i]] := t[i] - ASCII of 'a'
return true
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isIsomorphic(string s, string t) {
vector<int> arr(256, -1);
vector<bool> visited(256, 0);
vector<bool> visited1(256, 0);
for (int i = 0; i < s.length(); i++) {
if (visited[s[i]] == 1 || visited1[t[i]] == 1) {
if (arr[s[i]] != t[i] - 'a') {
return false;
}
}
else {
visited[s[i]] = 1;
visited1[t[i]] = 1;
arr[s[i]] = t[i] - 'a';
}
}
return true;
}
};
main(){
Solution ob;
cout << (ob.isIsomorphic("sky","fry"));
}
输入
"sky","fry"
输出
1
