数据结构
网络
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 次浏览
广告