google-code-prettify

Showing posts with label string. Show all posts
Showing posts with label string. Show all posts

Sunday, 2 December 2012

Check if one string is permutation of another string

You have two strings and you need to decide if the first one is a permutation of the other one. The solution uses HashMap data structure where each symbol of the first string is stored as a key and its value is the number of times this symbol appears. Then you loop through the second string and for each character which is a key in the HashMap you decrease the number of times this character appeared in the first string. In the end if the two strings are permutations of each other,  you will end up with a HashMap with all values 0:

boolean arePermutations(String str1, String str2) {
    if (str1.length() != str2.length()) {
        return false;
    }
    HashMap hashMapChars = new HashMap();
    // enter the chars and the number of times each of them appears
    for (int i = 0; i < str1.length(); i++) {
        if (hashMapChars.containsKey(str1.charAt(i))) {
            int count = hashMapChars.get(str1.charAt(i));
            hashMapChars.put(str1.charAt(i), count + 1);
        } else {
            hashMapChars.put(str1.charAt(i), 1);   }
        }
    }
    // for each char in str2 decrease the value number
    for (int i = 0; i < str2.length(); i++) {
        if (hashMapChars.containsKey(str2.charAt(i))) {
            int count = hashMapChars.get(str2.charAt(i));
            count--;
            if (count < 0) {
                return false;
            }
            hashMapChars.put(str2.charAt(i), count);
            } else {
                return false;
            }
        }
        return true;
}

Saturday, 1 December 2012

Are all characters in a string unique?

Here are some Java implementations checking if all the characters in a string are unique. The first solution uses HashMap to store the characters of the string:

boolean hasAllUniqueChars(String str) {
    HashMap<Character, Object> hashMapChars = new HashMap<Character, Object>();
    for (int i = 0; i < str.length(); i++) {
        if (hashMapChars.containsKey(str.charAt(i))) {
            return false;
        } else {
            hashMapChars.put(str.charAt(i), null);
        }
    }
    return true;
}

The second one is the most trivial one and has time complexity O(n2). It uses two nested for loops:

boolean hasAllUniqueChars2(String str) {  
    for (int i = 0; i < str.length(); i++) {
        for (int j = 0; j < str.length(); j++) {
            if(i == j){
                continue;
            }
            if(str.charAt(i) == str.charAt(j)){
                return false;
            }
        }
    }
    return true;
}