Steven Blogs

面试题 01.02. 判定是否互为字符重排

01.02. 判定是否互为字符重排open in new window 简单

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

示例 1：

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

示例 2：

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

说明：

0 <= len(s1) <= 100
0 <= len(s2) <= 100

提示：

  1. 描述两个字符串是否互为字符重排的含义。现在，看看你提供的定义，你能否根据这个定义检查字符串
  2. 有一种解法需要O(NlogN)的时间。另一种解法需要使用一些.空间，但需要运行时间为O(N)
  3. 散列表有用吗
  4. 两个重排的字符串应该具有相同的字符，但顺序不同。你可以让它们的顺序一样吗？

解答

“重新排列后，变成另一个字符串” 根据题干提供的信息，得知

  1. s1 和 s2 应该长度相同
  2. s1 和 s2 中出现的字符的数量和类型应该相同

解法一： 自己写的，仅供参考；两次循环，标记符号，没有出现过的直接返回

public bool CheckPermutation(string s1, string s2) {
    if(s1.Length!=s2.Length)  // 长度不同返回false
        return false;
    bool isExist;  // 标记字符是否在第二个字符串出现过
    byte[] flags = new byte[s2.Length]; // 存储s1 在 s2中出现时的标记
    foreach(char ch in s1){ // 循环s1中的字符，在s2中出现位置后标记其位置
        isExist = false;
        for(int i=0;i<s2.Length;i++){
            if(ch==s2[i] && flags[i]==0) // 相等时且对应的标记位置为0 时，标记对应位置为 1，跳出当前循环
            {
                isExist=true;
                flags[i] = 1;
                break;
            }                    
        }
        if(!isExist)
            return false;
    }
    return true;
    /*
        bool[] flags = new bool[s2.Length]; // 存储s1 在 s2中出现时的标记
        foreach(char ch in s1){ // 循环s1中的字符，在s2中出现位置后标记其位置
            for(int i=0;i<s2.Length;i++){
                if(ch==s2[i] && !flags[i]){
                    flags[i] = true;
                    break;
                }                    
            }
        }
        foreach(bool isExist in flags){
            if(!isExist)
                return false;
        }
        return true;
    */
}

解法2： 来自大家的结合，统计字符数，最后保证所有的字符都是 0

public bool CheckPermutationV2(string s1, string s2)
{
    if (s1.Length != s2.Length)
        return false;

    byte[] flags = new byte[128];
    for (int i = 0; i < s1.Length; i++)
    {
        flags[s1[i]]++;
        flags[s2[i]]--;
    }

    for (int i = 0; i < flags.Length; i++)
    {
        if (flags[i] != 0)
            return false;
    }

    return true;
}

解法三：

public bool CheckPermutationV3(string s1, string s2)
{
    if (s1.Length != s2.Length)
        return false;

    Dictionary<char, byte> countDict = new Dictionary<char, byte>(s1.Length);
    for (int i = 0; i < s1.Length; i++)
    {
        if (countDict.ContainsKey(s1[i]))
            countDict[s1[i]]++;
        else
            countDict.Add(s1[i], 1);  
    }

    for (int i = 0; i < s2.Length; i++)
    {
        if (countDict.ContainsKey(s2[i]))
            countDict[s2[i]]--;
        else
            return false;
    }

    foreach (char curChar in countDict.Keys){
        if(countDict[curChar] != 0)
            return false;
    }

    return true;
}

总结

第二种是我目前觉得比较完善的，但是具体的需求还得看具体的分析啦。

C# 支持以下预定义整型类型open in new window：

C# 类型/关键字范围大小.NET 类型
sbyte-128 到 1278 位带符号整数System.SByte
byte0 到 255无符号的 8 位整数System.Byte
short-32,768 到 32,767有符号 16 位整数System.Int16
ushort0 到 65,535无符号 16 位整数System.UInt16
int-2,147,483,648 到 2,147,483,647带符号的 32 位整数System.Int32
uint0 到 4,294,967,295无符号的 32 位整数System.UInt32
long-9,223,372,036,854,775,808 到 9,223,372,036,854,775,80764 位带符号整数System.Int64
ulong0 到 18,446,744,073,709,551,615无符号 64 位整数System.UInt64
nint取决于平台带符号的 32 位或 64 位整数System.IntPtr
nuint取决于平台无符号的 32 位或 64 位整数System.UIntPtr
Contributors: FHL