242. Valid Anagram

發布時間：2023-06-13 17:53:58

題目描述（簡單難度）判斷兩個字符串是否是異構，也就是兩個字符串包含的字母是完全相同的，只是順序不一樣。思路分析49 題其實已經做過

題目描述（簡單難度）

判斷兩個字符串是否是異構，也就是兩個字符串包含的字母是完全相同的，只是順序不一樣。

思路分析

49 題其實已經做過了，當時是給很多字符串，然后把異構的字符串放到一組里。介紹了四種解法，這里就不細講了，直接寫代碼了。

解法一 HashMap

最通用的解法，通過 HashMap 記錄其中一個字符串每個字母的數量，然后再來判斷和另一個字符串中每個字母的數量是否相同。

public boolean isAnagram(String s, String t) {n HashMap<Character, Integer> map = new HashMap<>();n char[] sArray = s.toCharArray();n for (int i = 0; i < sArray.length; i++) {n int count = map.getOrDefault(sArray[i], 0);n map.put(sArray[i], count + 1);n }nn char[] tArray = t.toCharArray();n for (int i = 0; i < tArray.length; i++) {n int count = map.getOrDefault(tArray[i], 0);n if (count == 0) {n return false;n }n map.put(tArray[i], count - 1);n }nn for (int value : map.values()) {n if (value != 0) {n return false;n }n }n return true;n}

我們最后判斷了一下所有的 value 是否為 0，因為要考慮這種情況，abc 和 ab。

我們也可以在開頭判斷一下兩個字符串長度是否相同，這樣的話最后就不用判斷所有的 value 是否為 0 了。

public boolean isAnagram(String s, String t) {n if (s.length() != t.length()) {n return false;n }n HashMap<Character, Integer> map = new HashMap<>();n char[] sArray = s.toCharArray();n for (int i = 0; i < sArray.length; i++) {n int count = map.getOrDefault(sArray[i], 0);n map.put(sArray[i], count + 1);n }nn char[] tArray = t.toCharArray();n for (int i = 0; i < tArray.length; i++) {n int count = map.getOrDefault(tArray[i], 0);n if (count == 0) {n return false;n }n map.put(tArray[i], count - 1);n }nn return true;n}

解法二排序

把兩個字符串按照字典序進行排序，排序完比較兩個字符串是否相等。

public boolean isAnagram(String s, String t) {n char[] sArray = s.toCharArray();n Arrays.sort(sArray);n s = String.valueOf(sArray);nn char[] tArray = t.toCharArray();n Arrays.sort(tArray);n t = String.valueOf(tArray);nn return s.equals(t);n}

解法三素數相乘

把每個字母映射到一個素數上，然后把相應的素數相乘作為一個 key 。

public boolean isAnagram(String s, String t) {n int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,n 101 };n char[] sArray = s.toCharArray();n int sKey = 1;n for (int i = 0; i < sArray.length; i++) {n sKey = sKey * prime[sArray[i] - 'a'];n }nn char[] tArray = t.toCharArray();n int tKey = 1;n for (int i = 0; i < tArray.length; i++) {n tKey = tKey * prime[tArray[i] - 'a'];n }nn return sKey == tKey;n}

49 題這樣寫是可以的，但當時也指出了一個問題，相乘如果數過大的話會造成溢出，最后的 key 就不準確了，所以會出現錯誤。

這里的話用 int 就不可以了，改成 long 也不行。最后用了 java 提供的大數類。

import java.math.BigInteger;nclass Solution {n public boolean isAnagram(String s, String t) {n int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,n 101 };n char[] sArray = s.toCharArray();n BigInteger sKey = BigInteger.valueOf(1);n for (int i = 0; i < sArray.length; i++) {n BigInteger temp = BigInteger.valueOf(prime[sArray[i] - 'a']);n sKey = sKey.multiply(temp);n }nn char[] tArray = t.toCharArray();n BigInteger tKey = BigInteger.valueOf(1);n for (int i = 0; i < tArray.length; i++) {n BigInteger temp = BigInteger.valueOf(prime[tArray[i] - 'a']);n tKey = tKey.multiply(temp);n }nn return sKey.equals(tKey);n }n}

解法四數組

這個本質上和解法一是一樣的，因為字母只有 26 個，所以我們可以用一個大小為 26 的數組來統計每個字母的個數。

因為有 26 個字母，不好解釋，我們假設只有 5 個字母，來看一下怎么完成映射。

首先初始化 key = "0#0#0#0#0#"，數字分別代表 abcde 出現的次數，# 用來分割。

這樣的話，"abb" 就映射到了 "1#2#0#0#0"。

"cdc" 就映射到了 "0#0#2#1#0"。

"dcc" 就映射到了 "0#0#2#1#0"。

public boolean isAnagram(String s, String t) {n int[] sNum = new int[26];n // 記錄每個字符的次數n char[] sArray = s.toCharArray();n for (int i = 0; i < sArray.length; i++) {n sNum[sArray[i] - 'a']++;n }n StringBuilder sKey = new StringBuilder();n for (int i = 0; i < sNum.length; i++) {n sKey.append(sNum[i] + "#");n }nn int[] tNum = new int[26];n // 記錄每個字符的次數n char[] tArray = t.toCharArray();n for (int i = 0; i < tArray.length; i++) {n tNum[tArray[i] - 'a']++;n }n StringBuilder tKey = new StringBuilder();n for (int i = 0; i < tNum.length; i++) {n tKey.append(tNum[i] + "#");n }nn return sKey.toString().equals(tKey.toString());n}