資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法學研究C++ 中的 K-相似字串
假設我們有兩個字串 A 和 B。如果我們可以精確交換 A 中兩個字母的位置 K 次（K 為非負整數），從而使結果字串為 B，則這兩個字串是 K-相似的。因此，我們有兩個字謎 A 和 B，我們需要找到使 A 和 B 成為 K-相似的最小 K 值。
例如，如果輸入為 A = "abc"，B = "bac"，則輸出為 2。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 swapp()，它將接收字串 s、i、j。
x := s[i]，y := s[j]
s[i] := y，s[j] := x
在主方法中執行以下操作：
如果 A 與 B 相同，則：返回 0
定義一個集合 visited
將 A 插入 visited
定義一個佇列 q，將 A 插入 q
從 lvl := 1 開始，當 q 不為空時，更新（lvl 加 1），執行：
sz := q 的大小
當 sz 不為零時，每次迭代 sz 減 1，執行：
curr := q 的第一個元素
從 q 中刪除元素
i := 0
當 (i < curr 的大小且 curr[i] 與 B[i] 相同) 時，執行：
(i 加 1)
從 j := i + 1 開始，當 j < curr 的大小時，更新 (j 加 1)，執行：
如果 curr[i] 與 curr[j] 相同，則：
忽略以下部分，跳到下一次迭代
如果 curr[j] 不等於 B[i]，則：
忽略以下部分，跳到下一次迭代
如果 curr[j] 與 B[j] 相同，則：
忽略以下部分，跳到下一次迭代
swapp(curr, i, j)
如果 curr 與 B 相同，則：
返回 lvl
如果 visited 中不包含 curr，則：
將 curr 插入 visited
將 curr 插入 q
swapp(curr, i, j)
返回 -1
讓我們來看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int kSimilarity(string A, string B) {
if (A == B)
return 0;
unordered_set<string> visited;
visited.insert(A);
queue<string> q;
q.push(A);
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
string curr = q.front();
q.pop();
int i = 0;
while (i < curr.size() && curr[i] == B[i])
i++;
for (int j = i + 1; j < curr.size(); j++) {
if (curr[i] == curr[j])
continue;
if (curr[j] != B[i])
continue;
if (curr[j] == B[j])
continue;
swapp(curr, i, j);
if (curr == B)
return lvl;
if (!visited.count(curr)) {
visited.insert(curr);
q.push(curr);
}
swapp(curr, i, j);
}
}
}
return -1;
}
void swapp(string &s, int i, int j) {
char x = s[i];
char y = s[j];
s[i] = y;
s[j] = x;
}
};
main(){
Solution ob;
cout << (ob.kSimilarity("abc", "bac"));
}輸入
"abc", "bac"
輸出
1
232 次瀏覽
