如何建设微信商城网站,房屋平面设计图制作软件,莱芜聊城网站建设,做百度关键词网站1 算法题 #xff1a;检查一个字符串是否是某个字符串的排列
1.1 题目含义
检查一个字符串是否是某个字符串的排列#xff0c;需要判断两个字符串是否由相同的字符组成#xff0c;且每个字符出现的次数也相同#xff0c;但是字符的顺序可以不同。简而言之#xff0c;如果…1 算法题 检查一个字符串是否是某个字符串的排列
1.1 题目含义
检查一个字符串是否是某个字符串的排列需要判断两个字符串是否由相同的字符组成且每个字符出现的次数也相同但是字符的顺序可以不同。简而言之如果能够通过对一个字符串中的字符进行重新排列使其与另一个字符串完全相同那么这两个字符串就是彼此的排列。
1.2 示例
示例 1: 输入
字符串1“anagram”字符串2“nagaram”
输出
true
解释
字符串 1 和字符串 2 都由字符’a’、‘n’、‘a’、‘g’、r’和’m’组成并且每个字符出现的次数也相同。虽然字符的顺序不同但它们仍然是彼此的排列。
示例 2: 输入
字符串1“listen”字符串2“silent”
输出
true
解释
字符串 1 和字符串 2 都由字符’l’、‘i’、‘s’、‘t’和’e’、n’组成注意’n’和’e’的顺序在两个字符串中是不同的并且每个字符出现的次数也相同。因此它们是彼此的排列。
示例 3: 输入
字符串1“hello”字符串2“world”
输出
false
解释
字符串 1 由字符’h’、‘e’、‘l’、‘l’和’o’组成而字符串 2 由字符’w’、‘o’、‘r’、‘l’和’d’组成。尽管两个字符串都包含字符’l’和’o’但它们包含的其他字符和字符的总数不同因此它们不是彼此的排列。
2 解题思路
解题思路如下
1初始化 首先需要两个字符串作为输入将其称之为 str1 和 str2。
2长度检查 首先检查两个字符串的长度是否相等。如果长度不等那么它们不可能是彼此的排列因为排列意味着字符的种类和数量都必须相同。
3字符计数 使用一个数据结构如数组或哈希表来统计 str1 中每个字符的出现次数。数组的大小通常是 26针对小写英文字母或 52针对小写和大写英文字母哈希表则没有这样的限制。
4比较字符计数 接下来遍历 str2 中的每个字符并在字符计数数据结构中减少对应字符的计数。如果任何时候某个字符的计数降到 0 以下或者某个字符在 str2 中不存在但在 str1 中存在即计数不为 0那么这两个字符串不是彼此的排列。
5检查结果 如果上述过程没有提前返回 false那么在遍历完 str2 之后可以得出结论两个字符串是彼此的排列因为它们的字符种类和数量都相同。
6返回结果 根据检查结果返回 true 或 false。
这个算法的时间复杂度是 O(n)其中 n 是字符串的长度因为只需要遍历每个字符串一次。空间复杂度取决于使用的数据结构如果使用固定大小的数组则空间复杂度为 O(1)对于固定大小的字母表如果使用哈希表则空间复杂度为 O(m)其中 m 是 str1 中不同字符的数量。
3 算法实现代码
3.1 使用哈希表
如下为算法实现代码
#include iostream
#include string
#include unordered_map class Solution
{
public:bool isPermutation(const std::string str1, const std::string str2){if (str1.length() ! str2.length()) {return false; // 如果长度不同则它们不可能是排列 }// 使用哈希表来统计字符出现次数 std::unordered_mapchar, int charCount;// 填充哈希表统计str1中每个字符的出现次数 for (char c : str1) {charCount[c];}// 遍历str2并在哈希表中减少对应字符的计数 for (char c : str2) {if (charCount[c] 0) {return false; // 如果字符在str2中存在但在str1中不存在返回false }charCount[c]--;}// 检查哈希表中是否还有计数不为0的字符 for (const auto pair : charCount) {if (pair.second ! 0) {return false; // 如果还有计数不为0的字符则它们不是排列 }}return true; // 所有检查都通过它们是排列 }
};上面代码首先检查两个字符串的长度是否相等如果不等则它们不可能是排列。接着使用 std::unordered_map哈希表来统计 str1 中每个字符的出现次数。然后遍历 str2并在哈希表中相应减少字符的计数。如果在遍历 str2 的过程中发现某个字符的计数已经为 0或者某个字符在 str1 中存在但在 str2 中不存在则返回 false。最后检查哈希表中是否还有任何非零的计数如果有则返回 false否则返回 true表示两个字符串是排列。
调用上面的算法并得到输出
int main()
{Solution ss;std::string str1, str2;// 测试用例1 str1 abc;str2 abc;std::cout Is \ str1 \ a permutation of \ str2 \? (ss.isPermutation(str1, str2) ? Yes : No) std::endl;// 测试用例2 str1 abc;str2 cab;std::cout Is \ str1 \ a permutation of \ str2 \? (ss.isPermutation(str1, str2) ? Yes : No) std::endl;// 测试用例3 str1 ;str2 ;std::cout Is \ str1 \ a permutation of \ str2 \? (ss.isPermutation(str1, str2) ? Yes : No) std::endl;// 测试用例4 str1 abcdefg;str2 abc;std::cout Is \ str1 \ a permutation of \ str2 \? (ss.isPermutation(str1, str2) ? Yes : No) std::endl;// 测试用例5 str1 abc, 12def;str2 c,12 abdef;std::cout Is \ str1 \ a permutation of \ str2 \? (ss.isPermutation(str1, str2) ? Yes : No) std::endl;// 测试用例6 str1 abcabcabc;str2 abcabcabc;std::cout Is \ str1 \ a permutation of \ str2 \? (ss.isPermutation(str1, str2) ? Yes : No) std::endl;return 0;
}上面代码的输出为
Is abc a permutation of abc? Yes
Is abc a permutation of cab? Yes
Is a permutation of ? Yes
Is abcdefg a permutation of abc? No
Is abc, 12def a permutation of c,12 abdef? Yes
Is abcabcabc a permutation of abcabcabc? Yes3.2 使用排序算法
可以使用排序算法来检查两个字符串是否是彼此的排列。如果两个字符串是彼此的排列那么它们包含相同的字符不考虑顺序因此如果将它们排序排序后的字符串应该是相同的。
如下为算法实现代码
#include iostream
#include string
#include algorithm // 为了使用sort函数 class Solution
{
public:bool isPermutation(const std::string str1, const std::string str2){if (str1.length() ! str2.length()) {return false; // 长度不同的字符串不可能是排列 }// 创建两个字符串的副本以便排序它们而不改变原始字符串 std::string sortedStr1 str1;std::string sortedStr2 str2;// 对两个字符串进行排序 std::sort(sortedStr1.begin(), sortedStr1.end());std::sort(sortedStr2.begin(), sortedStr2.end());// 比较排序后的字符串是否相同 return sortedStr1 sortedStr2;}
};在这个实现中首先检查两个字符串的长度是否相等。如果不等则它们不可能是排列。然后创建两个字符串的副本并对它们进行排序。最后比较排序后的字符串是否相同。如果相同则原始字符串是彼此的排列。
这个算法的时间复杂度主要由排序算法决定通常是 O(n log n)其中 n 是字符串的长度。空间复杂度是 O(log n)对于比较排序算法如快速排序或归并排序或 O(n)对于原地排序算法如堆排序。
4 测试用例
以下是针对上面算法的测试用例确保覆盖各种情况
1两个长度相同且字符种类和数量都相同的字符串
字符串1“abc”字符串2“abc”预期输出true
2两个长度相同但字符顺序不同的字符串
字符串1abc字符串2cab预期输出true
3两个空字符串
字符串1空字符串字符串2空字符串预期输出true
4一个长字符串和一个短字符串
字符串1abcdefg字符串2abc预期输出false
5包含特殊字符的字符串
字符串1abc, 12def字符串2c,12 abdef预期输出true
6包含重复字符的字符串
文本串abcabcabc子串aaabbbccc预期输出true
