数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学统计从给定数组中交换字符串对的第一个字符后可以获得的新字符串对的数量
在这个问题中，我们需要选择字符串对并交换它们的第一个字符。之后，我们需要计算新对的总数。我们可以通过交换每对的第一个字符并检查它是否存在于数组中来解决这个问题。
解决这个问题的有效方法是使用哈希表数据结构。
问题陈述 – 我们给定一个包含 N 个字符串的数组。我们可以从所有数组元素中取出任意两个字符串，并交换两个字符串的第一个字符。我们需要计算新生成的字符串对的总数，这些字符串对不在数组中。
示例
输入 – array[] = {"should", "would", "can"};
输出 – 3
解释 – 新生成的字符串对可以是 "could" 和 "wan"。另一个对可以是 "whould" 和 "sould"。第三个对可以是 "san" 和 "chould"。
输入 – array[] = {"demo", "test"};
输出 – 1
解释 – 不存在于数组中的新生成的字符串对是 "temo" 和 "dest"。
方法一
在这种方法中，我们将使用两个嵌套循环来获取数组元素的所有对。之后，我们将交换两对的第一个字符。接下来，我们将使用第三个嵌套循环来检查数组是否包含该对。
算法
定义变量 ‘cnt’ 并初始化为 0，以存储对的总数。
使用两个嵌套循环遍历字符串数组并获取每对数组元素。
获取当前对的两个字符串。
如果两个字符串的第一个字符不相等，则交换它们。
定义变量 ‘isFirst’ 和 ‘isSecond’，并初始化为 false，以跟踪新生成的字符串是否出现在数组中。
使用第三个嵌套循环检查新生成的字符串是否在数组中。根据数组中的字符串更新 ‘isFirst’ 和 ‘isSecond’ 变量的值。
如果两个字符串都不在数组中，则将 ‘cnt’ 的值增加 1。
返回 ‘cnt’ 变量的值。
示例
#include <iostream>
using namespace std;
// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
// Stores the count of pairs
int cnt = 0;
// Get all the pairs of strings
for (int i = 0; i < len; i++){
for (int j = i + 1; j < len; j++){
// store single pair of strings
string first = array[i], second = array[j];
// If both strings' first characters are not equal, swap them.
if (first[0] != second[0]){
swap(first[0], second[0]);
bool isFirst = false;
bool isSecond = false;
// Check whether the strings are present in the array or not
for (int k = 0; k < len; k++){
if (array[k] == first){
isFirst = true;
}
if (array[k] == second){
isSecond = true;
}
}
// If both the strings are present in the array, then increment the cnt by 1
if (isFirst == false && isSecond == false){
cnt++;
}
}
}
}
return cnt;
}
int main(){
string array[] = {"should", "would", "can"};
int N = sizeof(array) / sizeof(array[0]);
cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
return 0;
}
输出
Total number of new pairs we can generate by swapping the first characters of given strings is 3
时间复杂度 – O(N^3)，因为我们使用了三个嵌套循环。
空间复杂度 – O(1)
方法二
在这种方法中，我们将使用 map 数据结构将所有数组值存储到 map 中。之后，我们可以检查 map 是否包含新生成的字符串。如果不是，我们可以将计数器值增加 1。
算法
定义变量 ‘cnt’
遍历字符串数组，并将所有数组值存储到 map 中。
使用两个嵌套循环获取数组元素的所有对。
获取字符串对并将它们存储在 ‘first’ 和 ‘second’ 变量中。
如果两个字符串的第一个字符不相等，则交换它们。
在 map 中检查它是否包含新生成的字符串。如果不是，则将 ‘cnt’ 的值增加 1。
返回 ‘cnt’ 值。
示例
#include <iostream>
#include <unordered_map>
using namespace std;
// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
// to store the total number of new pairs
int cnt = 0;
// add all strings to the array map
unordered_map<string, int> str_map;
for (int i = 0; i < len; i++){
str_map[array[i]]++;
}
//find all pairs of strings that can be formed by swapping the first character of the strings
for (int i = 0; i < len; i++){
for (int j = i + 1; j < len; j++){
// get the current pair of strings
string first = array[i];
string second = array[j];
// If the first character of both strings is not the same, then swap them
if (first[0] != second[0]){
swap(first[0], second[0]);
// If both strings are not present in the map, then the increment count
if (str_map[first] == 0 && str_map[second] == 0){
cnt++;
}
}
}
}
return cnt;
}
int main(){
string array[] = {"should", "would", "can"};
int N = sizeof(array) / sizeof(array[0]);
cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
return 0;
}
输出
Total number of new pairs we can generate by swapping the first characters of given strings is 3
时间复杂度 – O(N^2)，因为我们使用了两个嵌套循环。
空间复杂度 – O(N)，因为我们使用 map 来存储所有数组元素。
我们学习了通过交换任何数组元素的第一个字符来生成的新对的总数。我们在第二种方法中优化了时间复杂度，但第一种代码在空间复杂度方面更好。
84 次浏览
