Check if an array of strings has all elements to create a given word

Question

Say you have an array of words

String[] arr = {"i", "a", "am", "good", "program", "gram"};

And a given key

String key = "iamgood";

boolean allWordsFound(arr, key){

// should return true if all possible words from array make up the key.
// e.g. keys matched {"i", "am", "good"};

} 

My approach :

boolean workbreak(String[] arr, String key) {

StringBuilder tempStr = new StringBuilder();
String[] possibleValues;
int count = 0;

 for(i = 0; i < key.length()- 1; i++){
     tempStr.append(key[i]);
     for(j =0; j < arr.length(); j++){
         tempStr == arr[j]{
             return true;
             //possibleValues[count] = tempStr;
             //count++;
         }
     }
 }

}

I am unable to figure out an approach. I do not need code but can you please suggest an algorithm.

Answer 1

Try the following:

Sort the String array by length, from longest to shortest:

{"i", "a", "am", "good", "program", "gram"};

becomes:

{"program","gram","good","am","a","i"}

The idea here is to match the longer words first, since in a case like this, you would want to match 'am' first before matching with 'a' (using the contains function).

Thus, the algorithm would check "program", then "gram", then "good" (matches), then "am" (matches), then "a", then "i" (matches).

The other solution is like bart.s stated in the comments: find all permutations, then check if any certain one matches. That will be a very slow algorithm though.