Break word (comprised of two or more words) into it's parts

Question

I have this problem to solve

There is an input word from user which has been formed from two different words like

AppleCake or BrownPie

Now we need to develop a program which will take this input and match it against a library of words and break the word into it's meaningful parts i-e Apple and Cake

Input:AppleCake

Output:This input has two words Apple and Cake

Input: RedGrapesWine

Output: This Input has three words Red, Grapes and Wine

My question is:

How should I start working on this problem?

Can anyone help me with pseudoCode/ Steps towards its solution?

there are good-smelling _regular expressions_ for your problem. — Juvanis, Oct 24 '12 at 09:55
is `applecake` an acceptable input? what about `sfadfApple`? — Denis Tulskiy, Oct 24 '12 at 10:01
Library can be of any size .. Only complete words are acceptable no misspelled word would be entertained. — Just_another_developer, Oct 24 '12 at 10:11
http://stackoverflow.com/questions/3752636/java-split-string-when-an-uppercase-letter-is-found mb this will help you.. — nkukhar, Oct 24 '12 at 10:18
possible duplicate of [Java Dictionary Searcher](http://stackoverflow.com/questions/5922956/java-dictionary-searcher) — Denis Tulskiy, Oct 24 '12 at 10:48
solution given in a duplicate question should work for you. its complexity is (I think) O(N^2) and does not depend on vocabulary size, given that vocabulary lookup is constant time. — Denis Tulskiy, Oct 24 '12 at 10:51

mkhelif · Accepted Answer · 2012-10-24T11:28:09.800

A very simple approach that works only if you have little number of words is to iterate through the words list and try to match word by word.

This is a very basic example (does not handle case, nor multiple occurrences of word or whatever), but it shows you how to do:

String input = readFromUser();
String[] dictionary = new String[] { "Apple", "Cake" };
List<String> found = new ArrayList<>();
for (String word : dictionary) {
    int index = input.indexOf(word);
    if (index >= 0) {
        input = input.substring(0, index) + input.substring(index + word.length());
        found.add(word);
    }
}
System.out.println("Found " + found.size() + " words: " + found);

This is very simple approach since its time consuming.

Another approach would be to have a Trie and navigate it until you find the right word (should be a better approach).

score 1 · Answer 2 · answered Oct 25 '12 at 06:34

To improve the algorithm, you should first create a set containig all the word-beginings your dictionary contains. If "Apple" and "Cake" are in the dictionary, the set has to contain "A", "Ap", "App", "Appl", "Apple", "C", "Ca" and "Cake".

So you will see sooner if a token cannot be a word, as it begining do not matches with the begining of a known word.

score 0 · Answer 3 · answered Oct 24 '12 at 09:58

0

If new words are using capital letters, you can use it to break word into pieces you want.

answered Oct 24 '12 at 09:58

Tom11

2,419
8
30
56

this is not mandatory that each new word starts with capital letter. – Just_another_developer Oct 24 '12 at 10:11
I think the OP was asking more for "how", though. – Dave Newton Oct 24 '12 at 10:12
@Sobia What about words that contain other words? – Dave Newton Oct 24 '12 at 10:13
@Sobia: If new words does not starts with capital then how would you read nowhere? as NoWhere or NowHere? – Parth Soni Oct 24 '12 at 10:16

score 0 · Answer 4 · answered Oct 24 '12 at 10:23

0

A simple solution will be to test every possible partition against a hashmap/dictionary.

e.g.

thebody -> t hebody (do t and hebody exist?), th ebody (th and ebody?), the body (the and body?), etc.

answered Oct 24 '12 at 10:23

james.haggerty

1,170
6
10

Break word (comprised of two or more words) into it's parts

4 Answers4