当前位置：首页 > news >正文

每日一题（二）：判断一个字符串是否是另一个字符串的排列

news 2025/1/13 16:37:55

目录

一、题目

二、题目分析

（一）明确需求

（二）分析思路

三、将思路转变为一个程序

C++代码

C代码

注释：

四、总结

一、题目

实现一个算法来识别一个字符串str2是否是另一个字符串str1的排列。

排列的解释如下：如果将str1的字符拆分开，重新排列后再拼接起来，能够得到str2，那么就说字符串str2是字符串str1的排列。

要求：不忽略大小写。

输入描述：第一行为字符串str1；第二行为字符串str2；字符串长度不超过100。

输入描述：如果str2字符串是str1字符串的排列，则输出 YES；如果str2字符串不是str1字符串的排列，则输出 NO.

二、题目分析

（一）明确需求

根据题目描述，我们要设计一个算法，以此判断一个字符串是否是另一个字符串的排列，算法要求不忽略大小写。那么我们首先要考虑的便是大小写是否按相同来算，例如“aB”是否是“ba”的排序？先说结果不算是其排列。因为根据题目对排列的解释如果字符串str1是字符串str2的排列，则将字符串str1拆开再组合可以得到str2，但是我们知道只有不改变大小写“aB”无论怎么组合都变成不了“ba”。其次题目存在输入描述和输出描述，且描述与我们上一篇博客的题相差不多所以这次我们简单罗列一下要点：

1、为了接收数据，我们需要设置两个最大可以包含100字符的字符数组。

2、返回的结果YES或NO要注意符合题目要求大写。

（二）分析思路

对于这题”关于两个字符串中一个字符串是否是另一个字符串的排列“问题的分析，我们首先可以从排序的解释中入手，重点关注”拆开后拼接“，可以理解为是一个指定大小字符串中的字符的“排列问题”，当然这里的重点不是说这个字符排列有多少中结果，而是我们可以了解到：当两个字符串是排列关系时，字符串str1中的字符的排列中必然有一个排列结果即是str2，而且还可以进一步推出str1中的字符的某一个有代表性的排列结果，必然是str2的字符的某一种具有同一代表特性的排列结果。

当然这句话比较拗口，很多人也不理解这句话和理解这道题有什么关联。那我用另一句话来描述：如果我们有一种方法能够得到字符排列中有代表性的排列结果，就可以通过这个具有代表性的排列结果的比较来判断两个字符串是否存在排列关系。具象化的解决思路便是：我们可以通过对字符进行升序或降序的排序（这是方法），得到它们具有代表性的一种排列结果（代表型结果便是字符全是递增或递减顺序的），通过对这个具有代表性的排列结构的比较便可以得到它们是否存在排列关系。

三、将思路转变为一个程序

同样的，本次仍然使用C与C++这两种语言来书写代码。

C++代码

#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;int compare(const void* a, const void* b)//自定义字符比较函数
{int ret = 0;if (*(char*)a > *(char*)b){ret = 1;}else if (*(char*)b < *(char*)a){ret = -1;}else{ret = 0;}return ret;
}int main()
{char str1[100];char str2[100];cin >> str1;cin >> str2;int num1 = strlen(str1);int num2 = strlen(str2);if (num1 == num2){qsort(str1, num1, 1, compare);qsort(str2, num1, 1, compare);int ret = strcmp(str1, str2);if (ret == 0){cout << "YES" << endl;}else{cout << "NO" << endl;}}else{cout << "NO" << endl;}return 0;
}

C代码

#include <string.h>
#include <stdlib.h>int compare(const void* a, const void* b)
{int ret = 0;if (*(char*)a > *(char*)b){ret = 1;}else if (*(char*)b < *(char*)a){ret = -1;}else{ret = 0;}return ret;
}int main()
{char str1[100];char str2[100];scanf("%s", str1);scanf("%s", str2);int num1 = strlen(str1);int num2 = strlen(str2);if (num1 == num2){qsort(str1, num1, 1, compare);qsort(str2, num1, 1, compare);int ret = strcmp(str1, str2);if (ret == 0){printf("YES\n");}else{printf("NO\n");}}else{printf("NO\n");}return 0;
}

注释：

为了方便高效对字符数组进行排序，博主使用了qsort函数，对于这个函数博主之前的博客并没有讲解，所以这里简单说一下，后期博主会专项讲解。

qsort函数是一个高效的排序函数，可以对任意数据类型进行排序，但前提是我们需要给出一个用于比较大小的函数作为依据。它需要传递四个参数，第一个参数表示要排序数据的指针，第二个参数是要排序数据的大小，第三个参数是该数据每个元素的大小，第四个是比较函数的指针。

除此之外，博主还使用了strlen函数来计算字符串大小，之前的博客对此函数有详细的讲解。