資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學檢查字串 A 是否可以透過將 A[i] 更改為 A[i+1] 或將 A[i]..A[i+K-1] 更改為 A[i]+1 來轉換為字串 B
給定兩個字串，我們必須檢查是否可以透過多次執行特定給定任務來將第一個字串轉換為另一個字串。這些任務只能對給定的第一個字串執行，並且任務是：
選擇任何索引 i，使得 i < length(A) -1，並將第 i 個字元與下一個字元交換。
給定一個整數 k，我們只能選擇第一個字串中任何連續的 k 個索引，如果它們相同，則可以將它們更新為下一個字元（如果可能，字元 'z' 不可以）。例如：可以將 'a' 更新為 'b'，'c' 更新為 'd'，'y' 更新為 'z' 等。
我們必須說明是否可以透過任意次數應用上述給定任務來使兩個給定字串相等。
示例
輸入
string str1 = “abcbcacba” string str2 = “xxxyyyzzz” int k = 3
輸出
Yes, it is possible to convert the first string to the second
解釋：第一個字串中有三個字元 a、b 和 c。此外，所有三個字元的頻率相同。我們可以將字元 'a' 的頻率一起增加到 'z'，因為第二個字串中有三個 'z'，同樣地，b 到 x，c 到 y。
輸入
string str1 = “abcbcacba” string str2 = “xxxzzzyyy” int k = 2;
輸出
No, it is not possible to convert the first string to the second
解釋：由於 k 的值為 2，我們只能對兩個字元進行分組，而我們不同的字元成對出現 3 個，因此無法更改它們。
觀察
我們必須使兩個字串相等，並且我們只能應用上述給定的操作。我們可以在這裡進行的觀察是：
我們可以任意多次交換字元，因此字元的順序無關緊要，唯一重要的是字元的頻率。
我們可以增加字元的頻率，而不能減少它，因此，如果有一些字元的 ASCII 值大於第二個字串中最大字元的 ASCII 值，那麼就不可能使兩個字串相同。
此外，如果兩個字串的大小不同，那麼顯然不可能使兩個字串相同。
方法
我們已經看到了問題的示例和觀察結果，讓我們轉到實現步驟。
首先，我們將檢查字串長度，如果字串長度不同，則不可能使它們相等，因此返回 false。
我們將建立兩個陣列來儲存兩個字串中字元的頻率。
然後，我們將使用 for 迴圈遍歷字串以獲取頻率。
之後，我們將使用一個額外的變數遍歷頻率陣列來計算剩餘的額外字元。
我們將使用 if-else 條件來檢查是否可以根據當前索引的頻率使字串與當前索引相同。
示例
#include <bits/stdc++.h>
using namespace std;
bool isPos(string str1, string str2, int k){
int len = str1.size(); // getting length of the string 1
// if the length of both the strings is not the same then return false
if(len != str2.size()){
return false;
}
// getting the frequency of the characters
int freq1[26] = {0};
int freq2[26] = {0};
// getting the frequencies
for(int i=0; i<len; i++){
freq1[str1[i]-'a']++;
}
for(int i=0; i<len; i++){
freq2[str2[i]-'a']++;
}
int cnt = 0; // maintaining count of the remaining characters
// traversing over the frequency array
for(int i=0; i<26; i++){
freq1[i] += cnt; // adding the previous characters which are more
if(freq2[i] > freq1[i]){
// we are not able to create the string
return false;
}
else if((freq1[i] - freq2[i]) % k){
// some characters lefts which are not multiple of k and we are not able to make them same of another
return false;
} else{
cnt += freq1[i]-freq2[i];
}
}
return true;
}
int main(){
// given string
string str1 = "abccbabca";
string str2 = "xxxzzzyyy";
int k = 3; // given number
// calling to the function
bool res = isPos(str1, str2, k);
if(res == true){
cout<<"Yes, it is possible to convert the first string to the second"<<endl;
} else{
cout<<"No, it is not possible to convert the first string to the second"<<endl;
}
}
輸出
Yes, it is possible to convert the first string to the second
時間和空間複雜度
上述程式碼的時間複雜度為 O(N)，其中 N 是給定字串的大小。
上述程式碼的空間複雜度為 O(1) 或常數，因為我們使用了額外的空間，但是該空間對於所有輸入大小都是常數。
結論
在本教程中，我們實現了一個程式來檢查如果我們在第一個字串上執行無限數量的給定操作，則是否可以使兩個給定字串相等。這些操作是：選擇任何索引 i，使得 i < length(A) -1，並將第 i 個字元與下一個字元交換；以及給定一個整數 k，我們只能選擇第一個字串中任何連續的 k 個索引，如果它們相同，則可以將它們更新為下一個字元。我們已經以線性時間和常數空間複雜度實現了該程式。
78 次檢視
