使用 Java 中的 HashMap 检查两个字符串是否为彼此的字谜

javaobject oriented programmingprogramming更新于 2024/9/16 6:04:17

字谜字符串是那些在每个字符串中都具有相同字符的字符串,只是排列顺序会发生变化。换句话说,如果一个字符串在重新排列另一个字符串的字符后形成了一个有意义的单词,则该字符串为字谜字符串。字谜字符串的一些示例是"cat and act"、"care and race"。它们都具有相同的字符及其频率。

在本文中,我们将讨论使用 Java 中的 HashMaps 检查两个字符串是否为彼此的字谜的方法。

问题陈述

给定两个字符串,我们需要使用 Java 中的哈希图检查这两个字符串是否为彼此的字谜。让我们举一个例子来更好地理解它。

输入:str1:care
    str2:race
输出:True

使用 Hashmap 检查字谜字符串的算法

  • 步骤 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 检查两个字符串是否为彼此的字母重排的技术。第一种方法使用两个哈希图来存储字符的频率,而第二种方法仅使用哈希图来解决问题陈述。


相关文章


有用资源