資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究執行 C++ 中的第二個字串的交換後，查詢兩個字串的最長公共字首
假設我們有兩個字串 str1 和 str2。在第二個字串上進行零次或多次操作後，查詢它們之間的最長公共字首。在每項操作中，我們可以交換任意兩個字母。因此，如果 str1 = “HERE”，str2 = “THERE”，則輸出將為 4。只需交換字元，就可以將第二個字串改寫為“HERET”。因此，最長字首的長度為 4。
如我們所知，我們只能交換 str2。並且矩陣的長度應最大化。所以這個想法是遍歷 str1 並檢查 str1 中當前字元的頻率是否與 str2 中相同或更低。如果相同，則在字串 a 中前進，否則中斷並列印字串 str1 中部分的長度，直到在字串 str2 中匹配一個字元為止。
示例
#include <iostream>
using namespace std;
void longestPrefix(string str1, string str2) {
int frequency[26]={0};
int a = str1.length();
int b = str2.length();
for (int i=0 ;i<b ; i++) {
frequency[str2[i] - 97] += 1;
}
int c = 0;
for (int i=0 ;i<a ; i++) {
if (frequency[str1[i] - 97] > 0){
c += 1;
frequency[str1[i] - 97] -= 1;
} else
break;
}
cout<<"Length of longest common prefix: " << c;
}
int main() {
string str1="here", str2 = "there";
longestPrefix(str1, str2);
}輸出
Length of longest common prefix: 4
更新於：2019-12-18
254 次瀏覽
廣告