Longest word made of other words in an array

Write a program to find the longest word made of other words.
EXAMPLE
Input: test, tester, testertest, testing, testingtester
Output: testingtester

Thoughts:

  1. Sort the array according to the length of the string. Longest first.
  2. Starting from the beginning of the resulted array, i.e., the longest string, for each word in the array:
    1. for each of the following word otherWord in the array, processing in order, i.e., from the longest to the shortest
    2. if word contains otherWord, delete otherWord from word and keep searching towards even shorter string.
    3. if at any step word becomes empty, meaning that it can be divided into several shorter words in the array, we should return it since that’s exactly what we wish to find.

Codes:

	public static class LengthComparator implements Comparator<String> {
		public int compare(String o1, String o2) {
			if (o1.length() < o2.length())
				return 1;
			else if (o1.length() > o2.length())
				return -1;
			else
				return 0;
		}
	}

	public static String longestWordMadeOfOtherWords(String[] words) {
		Arrays.sort(words, new LengthComparator());
		for (String word : words) {
			String backup = new String(word);
			for (String otherWord : words) {
				if (!otherWord.equals(backup) && word.contains(otherWord)) {
					word = word.replace(otherWord, "");
				}
			}
			if (word.length() == 0)
				return backup;
		}
		return null;
	}
Advertisements

1 Comment (+add yours?)

  1. Colin
    May 19, 2013 @ 02:16:20

    Hey, Runhe.
    I think this solution could not fit all cases. I could be wrong.
    Here is my thought.
    If input contains {“abcdefg”, “bcdef”, “bcde”, “fg”, “a”}
    abcdefg will not be found, since it will delete bcdef first.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: