使用 Java 中的 HashMap 檢查兩個字串是否互為字謎

---

字謎字串是指那些在每個字串中都具有相同字元的字串，只是它們的排列順序不同。換句話說，如果重新排列另一個字串的字元後形成一個有意義的單詞，則該字串就是一個字謎字串。一些字謎字串的示例是“cat 和 act”、“care 和 race”。它們都具有相同的字元及其頻率。

在本文中，我們將討論使用 Java 中的 HashMap 檢查兩個字串是否互為字謎的方法。

問題陳述

給定兩個字串，我們需要使用 Java 中的雜湊對映檢查這兩個字串是否互為字謎。讓我們舉一個例子來更好地理解它。

Input: str1: care
  str2: race
Output: True 

使用雜湊對映檢查字謎字串的演算法

• 步驟 1 − 如果兩個字串的長度不相等，則立即返回 false。

• 步驟 2 − 宣告兩個 HashMap。

• 步驟 3 − 遍歷第一個字串的元素，並將它們的頻率儲存到第一個雜湊對映中。

• 步驟 4 − 現在，遍歷第二個字串，並將它們的頻率儲存到第二個雜湊對映中。

• 步驟 5 − 現在，檢查兩個雜湊對映是否相等。

• 步驟 6 − 如果是，則返回 true。

• 步驟 7 − 否則，返回 false。

現在，讓我們討論一些檢查字謎字串的方法。

方法

• 方法 1 − 該方法使用兩個雜湊對映，並在不同的雜湊對映中儲存兩個字串的頻率計數。如果兩個雜湊對映相等，則這兩個字串互為字謎。

• 方法 2 − 在第二種方法中，只有一個雜湊對映。首先，第一個字串的頻率計數儲存在雜湊對映中，然後如果第二個字串中出現相同的字元，則遞減頻率。最後，如果雜湊對映的所有值都為零，則這兩個字串互為字謎，否則不是。

方法 1

在這種方法中，我們將討論程式程式碼，以使用 Java 中的兩個 HashMap 檢查兩個給定字串是否互為字謎。第一個雜湊對映儲存第一個字串的字元頻率，第二個雜湊對映儲存第二個字串的頻率。之後，我們檢查兩個雜湊對映是否相等，如果是，則字串是字謎，否則不是。

以下是相同的程式程式碼。

程式程式碼

import java.util.*;
public class Main 
{
	public static boolean checkAnagram(String s1, String s2)
	{
		if (s1.length() !=s2.length()) {
			return false;
		}
		
		//Declaration of the HashMaps
		HashMap<Character, Integer> mp1 = new HashMap<>();
	    	HashMap<Character, Integer> mp2 = new HashMap<>();
		for (int i = 0; i < s1.length(); i++) {
			if (mp1.containsKey(s1.charAt(i))) { 
				mp1.put(s1.charAt(i), mp1.get(s1.charAt(i)) + 1);
			}
			else {
				mp1.put(s1.charAt(i), 1);
			}
		}
		
		for (int i = 0; i < s2.length(); i++) {
			
			if (mp2.containsKey(s2.charAt(i))) {
				mp2.put(s2.charAt(i), mp2.get(s2.charAt(i)) + 1);
			}
			else {
				mp2.put(s2.charAt(i), 1);
			}
		}
	
		//Checking if the hashmaps are equal or not
		if(mp1.equals(mp2)){
		   return true;
		}
		else{
		   return false;
		}
	}
	public static void main(String[] args)
	{
		String a = "acra";
		String b = "cary";
		if (checkAnagram(a, b))
			System.out.print("True");
		else
			System.out.print("False");
   }
}

輸出

False

上述方法的複雜度如下所示 −

時間複雜度 − O(N)

空間複雜度 − O(2N)

方法 2

使用兩個雜湊對映會增加先前方法的複雜度，因此，現在我們將討論另一種方法，其中我們只使用一個雜湊對映並查詢字串是否互為字謎。

在這種方法中，我們將討論程式程式碼，以使用 Java 中的僅一個 HashMap 檢查兩個給定字串是否互為字謎。雜湊對映首先儲存第一個字串的字元頻率，然後遞減第二個字串的這些頻率。如果雜湊對映的值然後變為 0，則字串是字謎字串。

以下是相同的程式程式碼。

程式程式碼

import java.util.*;
public class Main 
{
	public static boolean checkAnagram(String s1, String s2)
	{
		if (s1.length() != s2.length()) {
			return false;
		}
		
		//Declaration of the HashMap
		HashMap<Character, Integer> mp = new HashMap<>();
	
		for (int i = 0; i < s1.length(); i++) {
			if (mp.containsKey(s1.charAt(i))) { 
				mp.put(s1.charAt(i), mp.get(s1.charAt(i)) + 1);
			}
			else {
				mp.put(s1.charAt(i), 1);
			}
		}
		for (int i = 0; i < s2.length(); i++) {
			if (mp.containsKey(s2.charAt(i))) { 
				mp.put(s2.charAt(i), mp.get(s2.charAt(i)) - 1);
			}
			else {
				return false;
			}
		}
		for (Character key : mp.keySet()) {
			if (mp.get(key) != 0) {
				return false;
			}
		}
		
		return true;
	}
	public static void main(String[] args)
	{
		String a = "care";
		String b = "race";

		if (checkAnagram(a, b))
			System.out.print("True");
		else
			System.out.print("False");
	}
}

輸出

True

上述方法的複雜度如下所示 −

時間複雜度 − O(N)

空間複雜度 − O(N)

結論

在本文中，我們討論了兩種使用 Java 中的 HashMap 檢查兩個字串是否互為字謎的技術。第一種方法使用兩個雜湊對映儲存字元的頻率，而第二種方法只使用一個雜湊對映來解決問題陳述。