Monday, December 8, 2014

Given two strings, write a method to decide if one is a permutation of the other. [Java]

Q. Given two strings, write a method to decide if one is a permutation of the other.

Algorithm:

1. Return false if strings have different lengths.
2. Count the frequency of occurrence of each character in string 1.
3. Match it with the frequency in string 2.
4. If each character has occurred the same number of times in both strings, return true else return false.

Source:


import java.util.HashMap;
import java.util.Map;

public class PermutationChecker {
    
    //method 1
    public static boolean isPermutation1(String s, String s2){ 
        
        if(s.length()!=s2.length())return false; 
        boolean[] check = new boolean[s2.length()];
        for(int i=0;i<s.length();++i){
            int j = 0;
            for(;j<s2.length();++j){
                if(!check[j] && s.charAt(i)==s2.charAt(j)){
                    check[j]=true;
                    break;
                }
            }
            if(j==s2.length())return false;
        }
        return true; 
    }
    
    //method 2
    public static boolean isPermutation2(String s, String s2){
        Map<Character, Integer> checker = new HashMap<>();
        
        for(char c:s.toCharArray()){
            if(!checker.containsKey(c))
                checker.put(c, 1);
            else 
                checker.put(c, checker.get(c)+1);
        }
        for(int i=0;i<s2.length();++i){
            char c = s2.charAt(i);
            if(!checker.containsKey(c))return false;
            else{
                int count = checker.get(c);
                if(count==0)return false;
                else checker.put(c, count-1);
            }
        }
        return true;
    }
    
    //method 3
    public static boolean isPermutation3(String s, String s2){
        if(s.length()!=s2.length())return false;
        int checker[] = new int[256];
        for(char c:s.toCharArray())checker[c]++;
        for(int i = 0;i<s2.length();++i){
            if(--checker[s2.charAt(i)]<0)return false;
        }
        return true;
    }
    public static void main(String[] args){
        String s = "cocacola";
        String s2 = "lacaccoo";
         
        System.out.println(isPermutation1(s, s2));
        System.out.println(isPermutation2(s, s2));
        System.out.println(isPermutation3(s, s2));
    }
}

Output:

true
true
true

No comments:

Post a Comment