2. Replace Words

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Example 3:

Input: dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
Output: "a a a a a a a a bbb baba a"

Example 4:

Input: dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 5:

Input: dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
Output: "it is ab that this solution is ac"

Solution: (Set)

class Solution
{
public:
    string replaceWords(vector<string> &dict, string sent)
    {

        set<string> s;

        for (int i = 0; i < dict.size(); i++)
        {
            s.insert(dict[i]);
        }

        string word = "";
        string res = "";

        for (int i = 0; i < sent.length(); i++)
        {
            if (sent[i] != 32)
            {
                word += sent[i];
            }
            else
            {
                bool found = false;
                for (int j = 1; j <= word.length(); j++)
                {
                    string k = word.substr(0, j);
                    if (s.find(k) != s.end())
                    {
                        res += k;
                        found = true;
                        break;
                    }
                }

                if (!found)
                {
                    res += word;
                }
                res += " ";
                word = "";
            }
        }

        bool found = false;
        for (int j = 1; j <= word.length(); j++)
        {
            string k = word.substr(0, j);
            if (s.find(k) != s.end())
            {
                res += k;
                found = true;
                break;
            }
        }

        if (!found)
        {
            res += word;
        }

        return res;
    }
};

Optimized Solution: (Trie)

class Solution
{
public:
    struct trieNode
    {
        char val;
        int endsHere;
        int count = 0;
        trieNode *child[26];
    };

    trieNode *createNode(char ch)
    {
        trieNode *temp = new trieNode;

        temp->val = ch;
        temp->endsHere = 0;
        temp->count = 0;

        for (int i = 0; i < 26; i++)
        {
            temp->child[i] = NULL;
        }

        return temp;
    }

    string replaceWords(vector<string> &dict, string sent)
    {
        trieNode *root;
        root = createNode('/');

        for (int i = 0; i < dict.size(); i++)
        {
            trieNode *cur = root;

            for (int j = 0; j < dict[i].length(); j++)
            {
                int ch = dict[i][j] - 97;
                if (cur->child[ch])
                {
                    cur->child[ch]->count++;
                }
                else
                {
                    cur->child[ch] = createNode(dict[i][j]);
                }
                cur = cur->child[ch];
            }

            cur->endsHere++;
        }

        string res = "";
        string word = "";
        
        for (int i = 0; i < sent.length(); i++)
        {
            if (sent[i] != 32)
            {
                word += sent[i];
            }
            else
            {
                trieNode *cur = root;
                bool flag = false;
                
                for (int j = 0; j < word.length(); j++)
                {
                    char ch = word[j];
                    if (cur->child[ch - 97])
                    {
                        cur = cur->child[ch - 97];
                        if (cur->endsHere > 0)
                        {
                            res += word.substr(0, j + 1);
                            flag = true;
                            break;
                        }
                    }
                    else
                    {
                        res += word;
                        flag = true;
                        break;
                    }
                }

                if (!flag)
                {
                    res += word;
                }

                res += " ";
                word = "";
            }
        }

        trieNode *cur = root;
        bool flag = false;
        for (int j = 0; j < word.length(); j++)
        {
            char ch = word[j];
            if (cur->child[ch - 97])
            {
                cur = cur->child[ch - 97];
                if (cur->endsHere > 0)
                {
                    res += word.substr(0, j + 1);
                    flag = true;
                    break;
                }
            }
            else
            {
                res += word;
                flag = true;
                break;
            }
        }

        if (!flag)
        {
            res += word;
        }

        return res;
    }
};