面试经典算法题68-有效的字母异位词

LeetCode.242

问题描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

**注意：**若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

思路

1. 初始化和检查长度：首先检查两个字符串的长度。如果长度不同，则直接返回 false，因为它们不可能是字母异位词。
2. 使用数组记录字符出现次数：用一个大小为26的整型数组来记录每个字符在字符串 s 中和字符串 t 中出现的次数。因为字符串只包含小写字母，所以数组大小为26就足够了。
3. 遍历两个字符串：遍历字符串 s 和 t。对于每个字符，更新数组中对应位置的计数。字符串 s 中的字符计数加1，字符串 t 中的字符计数减1。
4. 检查数组：最后遍历数组，如果所有的计数都为0，则说明两个字符串是字母异位词，否则不是。

参考代码

C++

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 判断两个字符串是否是字母异位词的函数
bool isAnagram(const string& s, const string& t) {
    // 如果长度不同，则不可能是字母异位词
    if (s.length() != t.length()) {
        return false;
    }

    // 用一个大小为26的数组记录每个字符的出现次数
    vector<int> charCount(26, 0);

    // 遍历字符串 s 和 t
    for (int i = 0; i < s.length(); ++i) {
        // 字符 s[i] 出现一次，计数加1
        charCount[s[i] - 'a']++;
        // 字符 t[i] 出现一次，计数减1
        charCount[t[i] - 'a']--;
    }

    // 检查数组中每个字符的计数是否为0
    for (int count : charCount) {
        if (count != 0) {
            return false;
        }
    }

    // 所有字符计数都为0，说明是字母异位词
    return true;
}

int main() {
    // 示例输入
    string s1 = "anagram";
    string t1 = "nagaram";
    string s2 = "rat";
    string t2 = "car";

    // 调用函数并输出结果
    cout << "s = \"" << s1 << "\", t = \"" << t1 << "\" -> " << (isAnagram(s1, t1) ? "true" : "false") << endl;
    cout << "s = \"" << s2 << "\", t = \"" << t2 << "\" -> " << (isAnagram(s2, t2) ? "false" : "false") << endl;

    return 0;
}

Java

import java.util.Arrays;

public class AnagramChecker {

    // 判断两个字符串是否是字母异位词的函数
    public static boolean isAnagram(String s, String t) {
        // 如果长度不同，则不可能是字母异位词
        if (s.length() != t.length()) {
            return false;
        }

        // 用一个大小为26的数组记录每个字符的出现次数
        int[] charCount = new int[26];

        // 遍历字符串 s 和 t
        for (int i = 0; i < s.length(); ++i) {
            // 字符 s.charAt(i) 出现一次，计数加1
            charCount[s.charAt(i) - 'a']++;
            // 字符 t.charAt(i) 出现一次，计数减1
            charCount[t.charAt(i) - 'a']--;
        }

        // 检查数组中每个字符的计数是否为0
        for (int count : charCount) {
            if (count != 0) {
                return false;
            }
        }

        // 所有字符计数都为0，说明是字母异位词
        return true;
    }

    public static void main(String[] args) {
        // 示例输入
        String s1 = "anagram";
        String t1 = "nagaram";
        String s2 = "rat";
        String t2 = "car";

        // 调用函数并输出结果
        System.out.println("s = \"" + s1 + "\", t = \"" + t1 + "\" -> " + (isAnagram(s1, t1) ? "true" : "false"));
        System.out.println("s = \"" + s2 + "\", t = \"" + t2 + "\" -> " + (isAnagram(s2, t2) ? "false" : "false"));
    }
}

Python

def is_anagram(s, t):
    # 如果长度不同，则不可能是字母异位词
    if len(s) != len(t):
        return False

    # 用一个大小为26的列表记录每个字符的出现次数
    char_count = [0] * 26

    # 遍历字符串 s 和 t
    for i in range(len(s)):
        # 字符 s[i] 出现一次，计数加1
        char_count[ord(s[i]) - ord('a')] += 1
        # 字符 t[i] 出现一次，计数减1
        char_count[ord(t[i]) - ord('a')] -= 1

    # 检查列表中每个字符的计数是否为0
    for count in char_count:
        if count != 0:
            return False

    # 所有字符计数都为0，说明是字母异位词
    return True

# 示例输入
s1 = "anagram"
t1 = "nagaram"
s2 = "rat"
t2 = "car"

# 调用函数并输出结果
print(f's = "{s1}", t = "{t1}" -> {is_anagram(s1, t1)}')
print(f's = "{s2}", t = "{t2}" -> {is_anagram(s2, t2)}')