使用 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 检查两个给定字符串是否互为字谜。第一个哈希映射存储第一个字符串的字符频率，第二个哈希映射存储第二个字符串的频率。之后，我们检查两个哈希映射是否相等，如果是，则字符串是字谜，否则不是。

以下是相同的程序代码。

程序代码

Open Compiler
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，则字符串是字谜字符串。

以下是相同的程序代码。

程序代码

Open Compiler
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)

Learn Java in-depth with real-world projects through our Java certification course. Enroll and become a certified expert to boost your career.

结论

在本文中，我们讨论了两种使用 Java 中的 HashMap 检查两个字符串是否互为字谜的技术。第一种方法使用两个哈希映射存储字符的频率，而第二种方法只使用一个哈希映射来解决问题陈述。

更新于: 2023-07-18

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告