Programming Challenge-II Adding spaces to a sentence

Let’s say you have a phrase without any spaces – eg. “thisisawesome”. Given a dictionary, how would you add spaces in this string?
Here is my simpler version

Build a set of all the words ( from a dictionary )
Have one pointer left, which points to start of the string
have another pointer right which pointers to the end of the string
try finding the word ( left .. right ) in the set
If found you got the word
if not, reduce right pointer by 1
goto step 4
if you find the word, move left equal to left + size of the word found
continue this till left is not equal to right.

#include <set>
#include <fstream>
#include <string>
#include <iostream>
std::set<std::string> pDict;
int BuildDictionary(const char *filename) {
    std::ifstream dictFile(filename);
    if ( dictFile.peek() == EOF ) {
        return -1;
    } 
    std::string line; 
    if (dictFile.is_open()) {
        while (! dictFile.eof() ) {  
            std::getline (dictFile,line);
            pDict.insert(line);
        }
        dictFile.close();
    } else {
        return EXIT_FAILURE;
    }
    return 0;
}

int main ( int argc, char **argv) {
    BuildDictionary(argv[1]);
    /*pDict.insert("i");
    pDict.insert("this");
    pDict.insert("saw");
    pDict.insert("is");
    pDict.insert("a");
    pDict.insert("some");
    pDict.insert("awesome");*/
    std::string word(argv[1]);
    std::string::iterator left = word.begin();
    std::string::iterator right = word.end();
    std::string::iterator rightMoving = left + 1;
    while ( left != right ) {        
        std::string tempWord(left, right);
        if ( pDict.find(tempWord) != pDict.end()) {
            std::cout << tempWord << " ";
            left = left + tempWord.size();
            right = word.end();
            continue;
        } else  {
            right--;
        }        
    }
    return 0;
}
Advertisements

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