笔试强训之每日一题(七)

判断是否互为字符重排

题目链接

题目描述

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

输入: s1 = “abc”, s2 = "bca"
输出: true

示例 2：

输入: s1 = “abc”, s2 = "bad"
输出: false

题目思路

当两个字符串的字符一样时，利用哈希的思想，将s1中对应字符在哈希表中对应位置++，将将s1中对应字符在哈希表中对应位置–，如果最后哈希表中的数组都为0，则确定其中一个字符串的字符重新排列后，能变成另一个字符串。否则不能

题目代码

class Solution {
public:
    bool CheckPermutation(string s1, string s2) 
    {
        int arr1[128] = {0};
        if(s1.size()!=s2.size())
        {
            return false;
        }
        for(int i = 0;i<s1.size();i++)
        {
            arr1[s1[i]]++;
            arr1[s2[i]]--;
        }
        for(int i = 0;i < 128;i++)
        {
            if(arr1[i]!=0)
            {
                return false;
            }
        }
        return true;
    }
};

回文排列

题目链接

题目描述

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。回文串不一定是字典当中的单词。

示例1：

输入："tactcoa"
输出：true（排列有"tacocat"、“atcocta”，等等）

题目思路

当字符串当中有两个或两个以上的奇数次字符时，则该字符串的重新排列不会是回文串，反之则该字符串的重新排列会是回文串，我们同样利用哈希的思想来解决，先统计字符的次数，然后看次数是奇数的有几个，如果有两个或两个以上，则不会是回文串，反之，则会是回文串。

题目代码

class Solution {
public:
    bool canPermutePalindrome(string s) {
        //哈希
        if(s.size() == 0)
        {
            return false;
        }
        int arr[128] = {0};
        for(int i = 0;i<s.size();i++)
        {
            arr[s[i]]++;//统计次数
        }
        int count = 0;
        for(int i = 0;i<128;i++)
        {
            if((arr[i]%2) == 1)//次数是奇数
            {
                count++;
            }
        }
        return count < 2;
    }
};