資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式：查詢K相似字串的K值
假設我們有兩個字串s和t。當我們可以精確交換s中兩個字母的位置K次，使得結果字串為t時，這兩個字串是K相似的。我們有兩個異位詞s和t，我們必須找到最小的K，使得s和t是K相似的。
因此，如果輸入類似於s = "abc"，t = "bac"，則輸出將為1。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式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，執行以下操作
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的count(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
更新於： 2021年10月7日
207 次檢視
廣告