Given two strings, write an algorithm to find if one string is a permutation (or anagram) of the other.
-
Definition: permutation (or anagram) denote two strings that have same characters (with same numbers), but in different order.
-
Example: LISTEN and SILENT (have same characters, but in different order).
Important Note!
-
Please mention approximate time complexity and space complexity. (At least if it is in order of n or n-square etc.).
-
Please post only working solutions (even if the complexity is not good).
-
Please indent properly.
public class AnagramStrings {
public static void main(String[] args) {
char []a=new char[]{'f','a','b','c'};
char []b=new char[]{'b','a','c','f'};
Arrays.sort(a);
Arrays.sort(b);
if(Arrays.equals(a, b)){
System.out.println("string are equal");
}
else{
System.out.println("strings are not anagrams....");
}
}
}
There are not any loops so according to me the time complexity should be O(n) .
Whenever you use library functions, you should consider their complexity as well. That is why many intervievers ask you not to use them. So what is the complexity of Arrays.sort in this case? You can do your research over google.
its O(n)2 , after research i think .
Average time complexity for most sorting algorithms will be n(log n). So can you try something with better complexity without using sorting.
Also, the question is about Strings, not char arrays. So you should have a method that takes in two String objects and returns a boolean. Internaly, you may then convert the string to a char array.
I am trying to use CharAt method .... but not getting proper results... i will post here if i get a correct output..
Here is a tip: Assume that the character set is ASCII as in the last solution @ http://javajee.com/forum-topic/find-out-if-a-string-has-all-unique-chara....
Also create a new comment when you have solution. Reply here if you have further questions or doubts.
Sir , this is the latest code working :
public class AnagramStrings {
public static void main(String[] args) {
System.out.println("the result is :" + match("helloo", "oollehfff"));
}
public static boolean match(String s1, String s2) {
int[] count = new int[255];
int[] count1 = new int[255];
for (int i = 0; i < count.length; i++) {
count[i] = 0;
count1[i] = 0;
}
for (int j = 0; j < s1.length(); j++) {
int h = s1.charAt(j);
count[h]++;
}
for (int j = 0; j < s2.length(); j++) {
int h = s2.charAt(j);
count1[h]++;
}
// boolean flag = true;
for (int i = 0; i < count1.length; i++) {
if (count[i] != count1[i]) {
return false;
}
}
return true;
}
}
Eventhough it can be improved with respect to naming and using library functions, this has a linear complexity in the order of n. Good work.
Thank you sir , i am feeling pumped after your appreciation . I will definetely try to improve the said areas of correctability by you sir. Sir , but i tried to use least number of library functions ... so how can we still reduce it sir ?
Actually I had thought the other way. Using Arrays.equals would be cleaner, but since this is an interview problem, the current solution is good without library functions.
Names can be more meaningful, but leave it for now as is and try with the next one...
After optimizing the above solution:
public class AnagramStrings {
public static void main(String[] args) {
System.out.println("the result is :" + match("helloo", "hello1"));
}
public static boolean match(String s1, String s2) {
int[] count = new int[255];
int[] count1 = new int[255];
if (s1.length() == s2.length()) {
for (int j = 0; j < s1.length(); j++) {
System.out.println(s1.charAt(j) + " - " + s2.charAt(j));
count[s1.charAt(j)]++;
count1[s2.charAt(j)]++;
}
} else {
return false;
}
// boolean flag = true;
for (int i = 0; i < s1.length(); i++) {
int index = s1.charAt(i);
if (count[index] != count1[index]) {
return false;
}
}
return true;
}
}
1) You don't need to initialize arrays since by default it takes '0' for int arrays.
2) You don't need to write two seperate for loops for 2 strings since we already know that the length of the 2 strings must match to satisfy anagram condition.
3) Lastly, to check count arrays are having same data or not.. you don't need to loop 255 times since we already know the index positions of count which we utilized(which are nothing but string characters)
Correct me if I am wrong?