資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的同構字串
假設我們有兩個字串 s 和 t；我們需要檢查它們是否同構。如果字串 s 中的字元可以替換成 t，則稱這兩個字串是同構的。
所有字元的出現必須替換為另一個字元，同時保持字元的順序。兩個字元不能對映到同一個字元，但一個字元可以對映到自身。
因此，如果輸入類似於 s = "egg"，t = "add"，則輸出將為 true，因為 e 可以對映到 a，g 可以對映到 d。
為了解決這個問題，我們將遵循以下步驟：
定義一個大小為 256 的陣列 arr 並填充 -1
定義一個大小為 256 的陣列 visited 並填充 0
定義一個大小為 256 的陣列 visited1 並填充 0
初始化 i := 0，當 i < s 的長度時，更新（i 增加 1），執行以下操作：
如果 visited[s[i]] 等於 1 或 visited1[t[i]] 等於 1，則：
如果 arr[s[i]] 不等於 t[i] - 'a' 的 ASCII 碼，則：
返回 false
否則
visited[s[i]] := 1
visited1[t[i]] := 1
arr[s[i]] := t[i] - 'a' 的 ASCII 碼
返回 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
更新於：2020年6月10日
3K+ 次檢視
廣告