Java: Determining if a word contains letters that can be found in another word?

Question

For example: If you have a String "magikarp", and you tested it against "karma", this would be true, because all of the letters that make up "karma" can be found in "magikarp".

"kipp" would return false, because there is only one "p" in "magikarp."

This is the attempt that I have right now, but I don't think it's very efficient, and it doesn't return correctly for cases when there are multiple occurrences of one letter.

private boolean containsHelper(String word, String word2){      
    for (int i = 0; i < word2.length(); i ++){
        if (!word.contains(String.valueOf(word2.charAt(i)))){
            return false;
        }
    }
    return true;
}

possible duplicate of [Check if letters that a word consists of are present in another string](http://stackoverflow.com/questions/22431351/check-if-letters-that-a-word-consists-of-are-present-in-another-string) — Leandro Carracedo, Feb 27 '15 at 03:11

score 2 · Accepted Answer · answered Feb 27 '15 at 03:08

I don't write the program here, but let you know how to do. There are 2 ways to do this considering complexity:

1) If you are sure that you would be getting only a-z/A-Z characters in the string, then take a array of size 26. Loop thorough the first string and place the count of the character appeared in the respective index. Say for example you have String "aabcc". Now array would look like [2,1,2,0,...0]. Now loop through the second String, and at each character, subtract the 1 from the array at the respective character position and check the resultant value. If value is less than 0, then return false. For example you have "aacd". When you are at d, you would be doing (0-1), resulting -1 which is less than 0, hence return false.

2) Sort the characters in the each String, and then compare.

chiwangc · Answer 2 · 2015-02-27T03:29:27.760

You need to ensure that for any character c that appears in the second string, the number of times that c appears in the second string is no greater than the number of times that c appears in the first string.

One efficient way to tackle this is to use a hashmap to store the count of the characters of the first string, and then loop through the characters in the second string to check whether their total count is no greater than that in the first string. The time and space complexity are O(n) in the worst case, where n is the length of the input strings.

Here is the sample code for your reference:

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

public class HashExample {

    public static void main(String[] args) {
        System.out.println(containsHelper("magikarp", "karma"));     // true
        System.out.println(containsHelper("magikarp", "kipp"));      // false    
    }

    private static boolean containsHelper(String word, String word2) {

        Map<Character, Integer> hm = new HashMap<>();

        for (int i = 0; i < word.length(); i++) {
            Character key = word.charAt(i);
            int count = 0;

            if (hm.containsKey(key)) {
                count = hm.get(key);
            }    
            hm.put(key, ++count);
        }

        for (int i = 0; i < word2.length(); i++) {
            Character key = word2.charAt(i);

            if (hm.containsKey(key)) {
                int count = hm.get(key);

                if (count > 0) {
                    hm.put(key, --count);
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}

Jean-François Savard · Answer 3 · 2015-02-27T03:22:44.643

Since you are only checking for characters, it would be more efficient to use indexOf and to check if it return -1 as contains itself call indexOf but with some other trims...

However, I think it would be simplier to convert the String to an array of char and to remove them if they are found which would also handle the case of multiple occurences.

So you're algorithm woud look something like this :

private final boolean containsHelper(final String word, final String word2)
{
    char[] secondWordAsCharArray = word2.toCharArray();
    char[] firstWordAsCharArray = word.toCharArray();

    Arrays.sort(firstWordAsCharArray);//Make sure to sort so we can use binary search.

    int index = 0;
    for(int i = 0; i++ < secondWordAsCharArray.length;)
    {
        index = Arrays.binarySearch(firstWordAsCharArray, secondWordAsCharArray[i]);//Binary search is a very performant search algorithm

        if(index == -1)
            return false;
        else
            firstWordAsCharArray[index] = ''; //A SENTINEL value, set the char a value you are sure that will never be in word2.
    }
}

Basically, what I do is :

Convert both word to char array to make it easier.
Sort the char array of the word we inspect so we can use binary search.
Loop over all characters of the second word.
retrieve the index using the binary search algorithm (a very performant algorithm on char, the best from my knowledge).
if index is -1, it was not found so we can return false.
else make sure we unset the character.

you'd need to sort the `firstWordAsCharArray` to use binary search on it — ciamej, Feb 27 '15 at 03:17

sprinter · Answer 4 · 2015-02-27T03:14:46.313

On possible algorithm is to remove all letters from your second word that don't occur in the first, sort both and then compare them.

Here is a reasonable way to achieve that in Java 8:

List<Integer> wordChars = word.chars().sorted().collect(Collectors.toList());
List<Integer> searchChars = search.chars()
    .filter(wordChars::contains).sorted().collect(Collectors.toList());
return wordChars.equals(searchChars);

Java: Determining if a word contains letters that can be found in another word?

4 Answers4