C++ 中使两个字符串成为变位词所需的最少步数

2025年3月21日 | 阅读 11 分钟

引言

字母异位词（Anagram）是指通过重新排列另一个单词或短语的字母而形成的单词或短语，通常使用所有原始字母恰好一次。例如，“listen”和“silent”这两个词是字母异位词。至于将两个字符串转换为字母异位词的问题，需要找到最少的移动次数，使得两个字符串在字符频率上匹配。

方法 1：简单方法

实施

 
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
int minStepsToMakeAnagram(const std::string &s1, const std::string &s2) {
    // Frequency arrays for each character in the alphabet
    std::vector<int> freq1(26, 0);
    std::vector<int> freq2(26, 0);
    // Count frequency of each character in s1
    for (char c : s1) {
        freq1[c - 'a']++;
    }
    // Count frequency of each character in s2
    for (char c : s2) {
        freq2[c - 'a']++;
    }
    // Calculate the number of changes required
    int steps = 0;
    for (int i = 0; i < 26; i++) {
        steps += std::abs(freq1[i] - freq2[i]);
    }
    // Since changes in one string can balance the other, we divide by 2
    return steps / 2;
}
int main() {
    std::string s1 = "listen";
    std::string s2 = "silent";
    std::cout << "Minimum steps to make the two strings anagram: " << minStepsToMakeAnagram(s1, s2) << std::endl;
    return 0;
}   

输出

 
Minimum steps to make the two strings anagram: 0

说明

步骤 1：频率计数
首先，我们需要了解每个字符在两个字符串中出现的频率。为此，我们创建两个数组（或列表），其中每个元素对应于字母表中的一个字符。为简单起见，我们将假设字符串只包含小写英文字母，因此每个数组将有 26 个元素，分别对应于从 'a' 到 'z' 的每个字母。
步骤 2：填充频率数组
接下来，我们遍历第一个字符串中的每个字符，并更新第一个频率数组中对应的位置。例如，如果第一个字符串包含字符 'a'，则我们在第一个数组中对应于 'a' 的位置增加计数。我们对第二个字符串及其对应的频率数组重复此过程。
步骤 3：计算差异
填充频率数组后，我们需要找出两个字符串之间有多少字符不同。对于每个字符（从 'a' 到 'z'），我们计算两个数组中它们频率的差异。这告诉我们需要添加或删除多少个特定类型的字符才能使频率匹配。
步骤 4：差异求和
一旦我们有了所有字符的差异，我们就将这些差异相加，得到所需的总字符更改次数。但是，由于一个字符串中的更改通常可以平衡另一个字符串中的更改，因此所需的实际步数是总差异的一半。

复杂度分析

时间复杂度

此解决方案的时间复杂度为 O(n)，其中 n 是两个字符串中较长字符串的长度。

计数频率：我们遍历两个字符串的每个字符来填充频率数组。此步骤每个字符串需要 O(n) 时间，总体为 O(n)。

计算差异：然后，我们遍历固定大小的频率数组（大小为 26）来计算差异并对其求和。此步骤需要 O(1) 时间，因为数组的大小是常数，不取决于输入字符串的长度。

由于计数和差异计算都是相对于字符串长度的线性运算，因此总体时间复杂度保持为 O(n)。

空间复杂度

此解决方案的空间复杂度为 O(1)。

频率数组：我们使用两个大小为 26 的固定大小数组来存储字符串中字符的频率计数。由于这些数组的大小不取决于输入大小，并且始终为 26（对于小写英文字母），因此被认为是 O(1) 空间。

其他变量：用于存储变量（如总步数）的其他空间是常数，并且不会随输入大小而增长。

因此，该算法使用恒定的额外空间，导致空间复杂度为 O(1)。

方法 2：使用排序

使用排序来解决使两个字符串成为字母异位词的问题涉及一种直接的方法，即利用字符的排序顺序轻松识别两个字符串之间的差异。字母异位词是可以通过重新排列而形成的字符串，这意味着一旦排序，两个字母异位词字符串将完全相同。

实施

 
#include <iostream>
#include <algorithm>
#include <string>
int minStepsToMakeAnagramUsingSorting(const std::string &s1, const std::string &s2) {
    // Sort both strings
    std::string sorted_s1 = s1;
    std::string sorted_s2 = s2;
    std::sort(sorted_s1.begin(), sorted_s1.end());
    std::sort(sorted_s2.begin(), sorted_s2.end());
    // Compare sorted strings to find differences
    int steps = 0;
    int i = 0, j = 0;
    while (i < sorted_s1.size() && j < sorted_s2.size()) {
        if (sorted_s1[i] != sorted_s2[j]) {
            steps++;
            // Move the pointer in the string that has the smaller character
            if (sorted_s1[i] < sorted_s2[j]) {
                i++;
            } else {
                j++;
            }
        } else {
            i++;
            j++;
        }
    }
    // Add remaining characters (if any)
    steps += (sorted_s1.size() - i) + (sorted_s2.size() - j);
    return steps;
}
int main() {
    std::string s1 = "listen";
    std::string s2 = "silentz";
    std::cout << "Minimum steps to make the two strings anagram (using sorting): "
              << minStepsToMakeAnagramUsingSorting(s1, s2) << std::endl;
    return 0;
}   

输出

 
Minimum steps to make the two strings anagram (using sorting): 1

说明

1. 步骤 1：输入字符串

您从两个输入字符串 s1 和 s2 开始。

2. 步骤 2：排序

排序过程：两个字符串（s1 和 s2）都会被排序。排序会重新排列每个字符串中的字符，使具有相同频率的字符以相同的顺序出现。

为什么排序：排序简化了比较过程，因为两个互为字母异位词的字符串在排序后将完全相同。

3. 步骤 3：比较

遍历排序后的字符串：排序后，您逐个字符地比较两个字符串，以确定它们之间有多少字符不同。

计数差异：对于排序后的字符串中的每个位置

如果当前位置的字符不同，则表示需要进行更改才能使字符串相同（字母异位词）。

每次字符不同时，增加计数器（步数）。

移动字母顺序上较小的字符所在的字符串的指针，以保持同步的比较。

4. 步骤 4：处理剩余字符

比较结束：比较完两个字符串中的字符后

两个字符串中未进行比较的任何剩余字符（由于长度不同）也计为必要的更改（步数）。

5. 步骤 5：结果

最少步数：steps 的最终值即为将一个字符串转换为另一个字符串的字母异位词所需的最小字符修改次数。

复杂度分析

时间复杂度

排序：此方法中的主要操作是对两个字符串进行排序。使用 Quicksort 或 Mergesort 等高效排序算法对长度为 n 的字符串进行排序通常具有 O(nlogn) 的时间复杂度。

比较：排序后，比较两个排序后的字符串需要遍历每个字符串一次，时间复杂度为 O(n)，其中 n 是较长字符串的长度。

因此，总体时间复杂度为 O(nlogn)，由排序步骤决定。

空间复杂度

排序：排序通常需要与被排序字符串长度成比例的额外空间。如果排序是原地进行的（使用空间复杂度为 O(1) 的 Quicksort 等算法），则空间复杂度为 O(1)。但是，某些排序算法在最坏情况下可能需要 O(n) 的额外空间。

额外空间：除了输入字符串之外，该算法还为计数器和迭代器等变量使用额外空间，这是 O(1) 的。

因此，考虑到用于排序和辅助存储的空间，此方法的空间复杂度通常在最坏情况下为 O(n)。

方法 3：使用哈希表

使用哈希表来解决使两个字符串成为字母异位词的问题，涉及计算两个字符串中每个字符的频率，然后比较这些频率。字母异位词的定义是具有相同频率的相同字符，尽管顺序不同。此方法利用哈希表（或关联数组）来有效计数字符出现次数并确定实现字母异位词所需的最小调整。

实施

 
#include <iostream>
#include <unordered_map>
#include <string>
int minStepsToMakeAnagramUsingHashMap(const std::string &s1, const std::string &s2) {
    // Hash maps to count character frequencies
    std::unordered_map<char, int> freq1, freq2;
    // Count frequencies in s1
    for (char c : s1) {
        freq1[c]++;
    }
    // Count frequencies in s2
    for (char c : s2) {
        freq2[c]++;
    }
    // Calculate differences
    int steps = 0;
    for (char c = 'a'; c <= 'z'; ++c) {
        steps += std::abs(freq1[c] - freq2[c]);
    }
    return steps;
}
int main() {
    std::string s1 = "listen";
    std::string s2 = "silentz";
    std::cout << "Minimum steps to make the two strings anagram (using hash map): "
              << minStepsToMakeAnagramUsingHashMap(s1, s2) << std::endl;
    
    return 0;
}   

输出

 
Minimum steps to make the two strings anagram (using hash map): 1

说明

6. 步骤 1：初始化

初始化两个 unordered_map 对象（freq1 和 freq2）。这些映射用于分别存储字符串 s1 和 s2 中每个字符的频率。

7. 步骤 2：计数频率

遍历字符串：遍历字符串 s1 中的每个字符。对于每个字符，增加其在 freq1 中的计数。

对 s2 重复：同样，遍历字符串 s2 中的每个字符并增加其在 freq2 中的计数。

为什么使用映射：使用映射可以实现 O(n) 的时间复杂度进行有效计数，其中 n 是字符串的长度。这是因为在无序映射中访问和更新元素通常平均为 O(1)。

8. 步骤 3：计算差异

遍历字符：遍历所有可能的字符（通常是 'a' 到 'z'）。

计算差异：对于每个字符，计算其在 freq1 和 freq2 中计数之间的绝对差异。

累加差异：将这些绝对差异相加，得到平衡 s1 和 s2 之间频率所需的总步数。

9. 步骤 4：结果

最终的总和（步数）代表将 s1 转换为 s2 的字母异位词所需的最小更改次数。

复杂度分析

时间复杂度

计数频率

遍历字符串 s1 和 s2 中的每个字符以更新哈希映射（freq1 和 freq2）的时间复杂度为 O(n)，其中 n 是 s1 和 s2 中较长字符串的长度。

计算差异

遍历哈希映射（通常最多 26 个条目，用于小写英文字母）并计算绝对差异的时间复杂度为 O(1)，因为唯一字符的数量是固定的。

总体时间复杂度

因此，总体时间复杂度为 O(n)，由遍历字符串以计数字符频率的操作决定。

空间复杂度

哈希映射

使用两个哈希映射（freq1 和 freq2）来存储 s1 和 s2 的字符频率。每个哈希映射的空间复杂度为 O(c)，其中 c 是字符集的大小（通常为 26，用于小写英文字母）。

附加空间

除了哈希映射之外，还为迭代器和计数器等变量使用额外空间，这是 O(1) 的。

总体空间复杂度

因此，总体空间复杂度为 O(c)，其中 c 是常数且通常很小（小写英文字母为 26）。

方法 4：使用双指针技术

使用双指针技术解决使两个字符串成为字母异位词的问题，涉及一种策略性方法，其中指针用于同时比较两个字符串中的字符。当与排序或频率计数结合使用时，此方法特别有效，并提供了线性时间复杂度的解决方案来识别两个字符串之间的差异。

实施

 
#include <iostream>
#include <algorithm>
#include <string>
int minStepsToMakeAnagramUsingTwoPointer(const std::string &s1, const std::string &s2) {
    // Sort both strings
    std::string sorted_s1 = s1;
    std::string sorted_s2 = s2;
    std::sort(sorted_s1.begin(), sorted_s1.end());
    std::sort(sorted_s2.begin(), sorted_s2.end());
    // Two pointers to traverse both sorted strings
    int steps = 0;
    int i = 0, j = 0;
    while (i < sorted_s1.size() && j < sorted_s2.size()) {
        if (sorted_s1[i] != sorted_s2[j]) {
            steps++;
            // Move the pointer in the string that has the smaller character
            if (sorted_s1[i] < sorted_s2[j]) {
                i++;
            } else {
                j++;
            }
        } else {
            i++;
            j++;
        }
    }
    // Add remaining characters (if any)
    steps += (sorted_s1.size() - i) + (sorted_s2.size() - j);
    return steps;
}
int main() {
    std::string s1 = "listen";
    std::string s2 = "silentz";
    std::cout << "Minimum steps to make the two strings anagram (using two-pointer technique): "
              << minStepsToMakeAnagramUsingTwoPointer(s1, s2) << std::endl;
    return 0;
}   

输出

 
Minimum steps to make the two strings anagram (using two-pointer technique): 1

说明

步骤 1：输入字符串
您从两个输入字符串 s1 和 s2 开始。
步骤 2：排序（可选）
排序过程：两个字符串（s1 和 s2）都可以选择性地进行排序。排序会重新排列每个字符串中的字符，使具有相同频率的字符以相同的顺序出现。
为什么排序：排序简化了比较过程，因为两个互为字母异位词的字符串在排序后将完全相同。
步骤 3：双指针策略
初始化：初始化两个指针（i 和 j）分别遍历 sorted_s1 和 sorted_s2。这些指针从每个排序字符串的开头开始。
比较：使用双指针同时遍历两个排序后的字符串
比较 sorted_s1 中 i 指向的字符和 sorted_s2 中 j 指向的字符。
如果字符不同，则递增计数器（steps），表示需要进行更改以使它们匹配（字母异位词）。
移动字母顺序上较小的字符的指针，以保持同步并继续比较。
步骤 4：处理剩余字符
比较结束：比较完两个字符串中的字符后
两个字符串中未进行比较的任何剩余字符（由于长度不同）也计为必要的更改（步数）。
步骤 5：结果
steps 的最终值即为将一个字符串转换为另一个字符串的字母异位词所需的最小字符修改次数。

示例

考虑字符串 "listen" 和 "silentz"

排序（可选）

排序后

"listen" 变为 "eilnst"
"silentz" 变为 "eilnstz"

双指针比较

使用双指针比较每个位置的字符

同时遍历两个排序后的字符串

比较 'e' 和 'e'（匹配），移动两个指针。
比较 'i' 和 'i'（匹配），移动两个指针。
比较 'l' 和 'l'（匹配），移动两个指针。
比较 'n' 和 'n'（匹配），移动两个指针。
比较 's' 和 's'（匹配），移动两个指针。
比较 't' 和 'z'（检测到差异），递增 steps 计数器。

结果

steps 将因不匹配（'t' vs 'z'）而增加 1，表示需要进行一次更改（添加 'z'）才能使字符串成为字母异位词。

复杂度分析

时间复杂度

排序（如果应用）

如果在开头使用了排序，则时间复杂度由排序步骤决定，该步骤为 O(nlogn)，其中 n 是 s1 和 s2 中较长字符串的长度。

双指针比较

排序后或直接进行，使用双指针的比较涉及遍历每个字符串一次，其时间复杂度为 O(n)，其中 n 是 s1 和 s2 中较长字符串的长度。

总体时间复杂度

因此，如果使用排序，总体时间复杂度为 O(nlogn)，如果不使用排序，则为 O(n)，但考虑到排序步骤，通常为 O(nlogn)。

空间复杂度

排序（如果应用）

根据所使用的排序算法，排序可能需要额外的空间。通常，n 是较长字符串的长度，则辅助空间为 O(n)。

双指针技术

双指针技术本身的空间复杂度为 O(1)，因为它只需要几个额外的变量（指针和计数器），这些变量不会随输入大小而扩展。

总体空间复杂度

考虑到排序步骤和变量的额外空间，在最坏情况下，总体空间复杂度为 O(n)，其中 n 是较长字符串的长度。

下一主题C++ 中的浮点数精度（floor()、ceil()、trunc()、round() 和 setprecision()）

C++ 中使两个字符串成为变位词所需的最少步数

引言

方法 1：简单方法

实施

说明

复杂度分析

方法 2：使用排序

实施

说明

复杂度分析

方法 3：使用哈希表

实施

说明

复杂度分析

方法 4：使用双指针技术

实施

说明

示例

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中使两个字符串成为变位词所需的最少步数

引言

方法 1：简单方法

实施

说明

复杂度分析

方法 2：使用排序

实施

说明

复杂度分析

方法 3：使用哈希表

实施

说明

复杂度分析

方法 4：使用双指针技术

实施

说明

示例

复杂度分析

相关帖子

C++ 中的笔分配问题

C++ Kasai 算法