Sunday 20 December 2020

Anagram Check of 2 strings

Given a program to check whether two strings are anagram or not. 

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 Example 1:

SILENT

LISTEN

Example 2:

aab

aba

In the above case both strings have same number of characters(characters used exactly once).


Solution:

Approach 1:
Time Complexity: O(n2)

Source code:

public class Main {
public static void main(String[] args)
{
String s="aaab",s2="abba";
boolean isAnagram=false,visited[]=new boolean[s2.length()];
if(s.length()==s2.length())
{
for(int i=0;i<s.length();i++)
{
char ch=s.charAt(i);
isAnagram=false;
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j)==ch&&visited[j]==false)
{
isAnagram=true;
visited[j]=true;
break;
}
}
if(!isAnagram)
break;
}
}
if(isAnagram)
System.out.println("Anagram");
else
System.out.println("Not an Anagram");
}
}

Approach 2:

Taking two 256 arrays and making a note of count at its respective indices.
Eg: if 'a' is encountered then index at 97 is increased.

public class Main
{
public static void main(String[] args)
{
String a="aab";
String b="aba";
boolean isAnagram=true;
int[] al=new int[256];
int[] bl=new int[256];

for(char c:a.toCharArray()){
int index=(int)c;
al[index]++;
}
for(char c:b.toCharArray()){
int index=(int) c;
bl[index]++;
}
for(int i=0;i<256;i++){
if(al[i]!=bl[i]){
isAnagram=false;
break;
}
}
if(isAnagram)
System.out.println("Anagram");
else
System.out.println("Not an anagram");
}
}



Approach 3:

Taking one integer array and when character encountered in first string the increment and after iterating second string decrement the same index. At last check whether all the elements in array are zeros.

public class Main
{
public static void main(String[] args)
{
String a="aab";
String b="aba";
boolean isAnagram=true;
int[] al=new int[256];

for(char c:a.toCharArray()){
int index=(int)c;
al[index]++;
}
for(char c:b.toCharArray()){
int index=(int) c;
al[index]--;
}
for(int i=0;i<256;i++){
if(al[i]!=0)
{
isAnagram=false;
break;
}
}
if(isAnagram)
System.out.println("Anagram");
else
System.out.println("Not an anagram");
}
}



No comments:

Post a Comment

Random password generator in Java

       Random password generator in Java Source code: mport java.io.*; import java.util.*; public class Main { public static void main(Str...