Check if one string is a permutation (or anagram) of the other

12 posts / 0 new
Last post
heartin
Check if one string is a permutation (or anagram) of the other

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!

  1. Please mention approximate time complexity and space complexity. (At least if it is in order of n or n-square etc.).

  2. Please post only working solutions (even if the complexity is not good).

  3. Please indent properly.

Tags: 
Was it useful?
huzefa
Anagram Strings

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) .

Was it useful?
heartin
Whenever you use library

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.

Was it useful?
huzefa
Anagram Strings

its O(n)2 , after research i think .

Was it useful?
heartin
So can you try something with

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.

Was it useful?
huzefa
using CharAt

I am trying to use CharAt method .... but not getting proper results...  i will post here if i get a correct output..

Was it useful?
heartin
Here is a tip: Assume that

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.

Was it useful?
huzefa
Edited Solution (Latest)

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;
    }

}

 

Was it useful?
heartin
Eventhough it can be improved

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. 

Was it useful?
huzefa
Thank You Sir

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 ?

Was it useful?
heartin
Actually I had thought the

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...

Was it useful?
clalam
After optimizing the above

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?

Was it useful?

Quick Notes Finder Tags

Activities (1) advanced java (1) agile (3) App Servers (6) archived notes (2) ArrayLists (1) Arrays (2) Best Practices (12) Best Practices (Design) (3) Best Practices (Java) (7) Best Practices (Java EE) (1) BigData (3) Chars & Encodings (6) coding problems (2) Collections (15) contests (3) Core Java (All) (53) course plan (2) Database (12) Design patterns (8) dev tools (3) downloads (2) eclipse (9) Essentials (1) examples (14) Exception (1) Exceptions (4) Exercise (1) exercises (6) Getting Started (18) Groovy (2) hadoop (4) hibernate (77) hibernate interview questions (6) History (1) Hot book (5) http monitoring (2) Inheritance (4) intellij (1) java 8 notes (4) Java 9 (1) Java Concepts (7) Java Core (8) java ee exercises (1) java ee interview questions (2) Java Elements (16) Java Environment (1) Java Features (4) java interview points (4) java interview questions (4) javajee initiatives (1) javajee thoughts (3) Java Performance (6) Java Programmer 1 (12) Java Programmer 2 (8) Javascript Frameworks (1) Java SE Professional (1) JPA 1 - Module (6) JPA 1 - Modules (1) JSP (1) Legacy Java (1) linked list (3) maven (1) Multithreading (16) NFR (1) No SQL (1) Object Oriented (9) OCPJP (4) OCPWCD (1) OOAD (3) Operators (4) Overloading (2) Overriding (2) Overviews (1) policies (1) programming (1) Quartz Scheduler (1) Quizzes (17) RabbitMQ (1) references (2) resources (1) restful web service (3) Searching (1) security (10) Servlets (8) Servlets and JSP (31) Site Usage Guidelines (1) Sorting (1) source code management (1) spring (4) spring boot (3) Spring Examples (1) Spring Features (1) spring jpa (1) Stack (1) Streams & IO (3) Strings (11) SW Developer Tools (2) testing (1) troubleshooting (1) user interface (1) vxml (8) web services (1) Web Technologies (1) Web Technology Books (1) youtube (1)