APT Syllable Sort

Class

public class SyllableSorting { public String[] sortWords(String[] words) { // you write code here } }

Problem Statement

Syllable sorting is a method of sorting words based on their syllabic decompositions. The first step is to decompose each word into syllables. A syllable is defined as a maximal non-empty substring of consonants followed by a maximal non-empty substring of vowels. The only vowels are 'a', 'e', 'i', 'o' and 'u'. All other letters are considered consonants. All words will start with a consonant and end with a vowel.

To compare two words syllabically, first decompose them into sequences of syllables. For example, the words "zcdbadaerfe" and "foubsyudba" decompose as follows:

"zcdbadaerfe" = {"zcdba", "dae", "rfe"}
"foubsyudba" = {"fou", "bsyu", "dba"}

Then, sort each sequence of syllables alphabetically. In the above example, the sequences become:

{"dae", "rfe", "zcdba"}
{"bsyu", "dba", "fou"}

Then, compare these sorted sequences lexicographically. A sequence S1 comes before a sequence S2 lexicographically if S1 has an alphabetically earlier element at the first index at which they differ. In the above example, the second sequence comes earlier lexicographically because "bsyu" comes before "dae" alphabetically.

If two sorted sequences are equal, then compare their corresponding unsorted sequences instead. For example, the words "daba" and "bada" decompose into the same sorted sequence {"ba", "da"}. Compare the unsorted sequences {"da", "ba"} and {"ba", "da"} to determine that "bada" comes before "daba".

You are given a String[] words. Sort the words using the method above and return the resulting String[].

Constraints

words will contain between 1 and 50 elements, inclusive.
Each element of words will contain between 2 and 50 characters, inclusive.
Each element of words will contain only lowercase letters ('a'-'z').
The first character of each element of words will be a consonant.
The last character of each element of words will be a vowel.

Examples

    
{"xiaoxiao", "yamagawa", "gawayama"}

Returns: {"gawayama", "yamagawa", "xiaoxiao" }

After decomposing the words into sequences of syllables, we get the following unsorted and sorted sequences of syllables:

   WORD    |    UNSORTED SEQUENCES    |     SORTED SEQUENCES
-----------+--------------------------+--------------------------
"xiaoxiao" | {"xiao", "xiao"}         | {"xiao", "xiao"}
"yamagawa" | {"ya", "ma", "ga", "wa"} | {"ga", "ma", "wa", "ya"}
"gawayama" | {"ga", "wa", "ya", "ma"} | {"ga", "ma", "wa", "ya"}

To compare "xiaoxiao" with the other two words, we use the sorted sequences of syllables. However, to compare "yamagawa" with "gawayama" we have to use the unsorted sequences because the sorted ones are equal.


{"bcedba", "dbabce", "zyuxxo"}

Returns: {"bcedba", "dbabce", "zyuxxo" }

    

{"hgnibqqaxeiuteuuvksi", "jxbuzui", "zrotyqeruiydozui",
 "ywuuzkto", "lmopbookoagyco", "vredfvavvexliu"}

Returns: 

{"hgnibqqaxeiuteuuvksi",
"vredfvavvexliu",
"lmopbookoagyco",
"jxbuzui",
"zrotyqeruiydozui",
"ywuuzkto" }


{"crazgo", "cwsoygiokiuo", "yueoseeu", "tuadiojvugeoe",
 "naumxditui", "sgukkelyoi", "nrohjuasoia", "mgabmo"}

Returns: 

{"mgabmo",
"crazgo",
"cwsoygiokiuo",
"tuadiojvugeoe",
"nrohjuasoia",
"sgukkelyoi",
"naumxditui",
"yueoseeu" }

```
{"wheewjuguoi", "coutcu", "hqivaa", "sgiibgwi", "ypaqpki",
 "bgyikouapae", "wqakeu", "skolfo", "pzesaa", "ypivhi"}

Returns: 

{"sgiibgwi",
"bgyikouapae",
"coutcu",
"wheewjuguoi",
"hqivaa",
"wqakeu",
"skolfo",
"pzesaa",
"ypaqpki",
"ypivhi" }
```
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2006, TopCoder, Inc. All rights reserved.