Data Structure and Algorithm - Detect Word Permutation

1. Problem Description
This is a Microsoft interview question for software develop engineer from careercup. Here is the original thread,
"

A list of words is given and a bigger string given how can we find whether the string is a permutation of the smaller strings.
eg- s= badactorgoodacting dict[]={'actor','bad','act','good'] FALSE
eg- s= badactorgoodacting dict[]={'actor','bad','acting','good'] TRUE
The smaller words themselves don't need to be permuted. The question is whether we can find a ordering of the smaller strings such that if concatenated in that order it gives the larger string
One more constraint - some words from dict[] may also be left over unused

- novicedhunnu September 15, 2016 in India | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
The solution is based on Trie data structure and algorithm. Details refer to my C++ post - Data Structure and Algorithm - Trie.

Pseudo-code:
    1. Save all word into Trie strucutre
    2. Initialize an empty queue/stack (breadth/depth-first search)
    3. Push starting index 0 into queue/stack (search from start of input string in Trie)
    4. Do until queue/stack is empty
        * Take the top value of queue/stack as idx and pop it out
        * Search input string starting from idx in Trie strucuture
            - Push ending index of any valid word starting from idx into queue/stack
            - Return TRUE, if 
                ~ reaching the end of input and 
                ~ having a valid word - [idx, endOfInputString)  in Trie
    5. Return FALSE otherwise

I have implemented this solution in both C++ and Python. The C++ implementation is provided in next section and the Python solution can be found on my Python post, Data Structure and Algorithm - Detect Word Permutation. Trie is a node-based data structure and algorithm. Therefore a recursive and non-recursive solution are implemented.

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
// PermutationDetector.h
#pragma once

#include <queue>
#include <string>
#include <vector>

struct DictionaryTrie;

class PermutationDetector
{
public:
    PermutationDetector();
    PermutationDetector(const std::vector<std::string> &words);
    ~PermutationDetector();

    void ConstructDict(const std::vector<std::string> &words, const bool appendMode);

    // recursive implementation
    bool IsPermutation_R(const std::string &word) const;
    // non-recursive implementation
    bool IsPermutation(const std::string &word) const;
private:
    bool IsPermutation_R(const std::string &word, std::queue<size_t> &nextSearch) const;
    DictionaryTrie *m_DictRoot;

};

// PermutationDetector.cpp
#include "PermutationDetector.h"
#include "DictionaryTrie.h"

#include <queue>

#include <cassert>

PermutationDetector::PermutationDetector()
    : m_DictRoot(nullptr)
{
}

PermutationDetector::PermutationDetector(const std::vector<std::string> &words)
    : m_DictRoot(nullptr)
{
    ConstructDict(words, false);
}

PermutationDetector::~PermutationDetector()
{
    if (m_DictRoot) {
        DestoryDictionaryTrie(m_DictRoot);
        m_DictRoot = nullptr;
    }
}

void PermutationDetector::ConstructDict(const std::vector<std::string> &words,
                                        const bool appendMode)
{
    if (!appendMode && m_DictRoot) {
        DestoryDictionaryTrie(m_DictRoot);
        m_DictRoot = nullptr;
    }
    if (!m_DictRoot) {
        m_DictRoot = new DictionaryTrie();
    }

    assert(m_DictRoot != nullptr);

    auto&& itEnd = words.rend();
    for (auto&& it = words.rbegin(); it != itEnd; ++it) {
        AddWord(m_DictRoot, it->c_str());
    }
}

bool PermutationDetector::IsPermutation_R(const std::string &word,
                                        std::queue<size_t> &nextSearch) const
{
    if (nextSearch.empty()) {
        return false;
    }

    const size_t startSearchIndex = nextSearch.front();
    const char *startSearchPtr = word.c_str() + startSearchIndex;
    nextSearch.pop();

    DictionaryTrie *tempPtr = m_DictRoot;
    size_t searchedLen = 1;
    while (*startSearchPtr != '\0' && tempPtr) {
        tempPtr = tempPtr->children[*startSearchPtr - 'a'];
        if (tempPtr && tempPtr->str) {
            // found a valid word/permutation and candidate for next search
            nextSearch.push(startSearchIndex + searchedLen);
        }
        ++searchedLen;
        ++startSearchPtr;
    }

    if (*startSearchPtr == '\0' && tempPtr && tempPtr->str) {
        return true;
    }

    // tail recursion
    return IsPermutation_R(word, nextSearch);
}

bool PermutationDetector::IsPermutation_R(const std::string &word) const
{
    if (word.empty()) {
        return false;
    }

    // switch queue/stack for breadth/depth-first search
    std::queue<size_t> nextSearch;
    nextSearch.push(0);
    return IsPermutation_R(word, nextSearch);
}

bool PermutationDetector::IsPermutation(const std::string &word) const
{
    if (word.empty()) {
        return false;
    }

    // switch queue/stack for breadth/depth-first search
    std::queue<size_t> nextSearch;
    nextSearch.push(0);
    while (!nextSearch.empty()) {
        size_t startSearchIndex = nextSearch.front();
        nextSearch.pop();
        const char *searchStartPtr = word.c_str() + startSearchIndex;
        DictionaryTrie *tempPtr = m_DictRoot;
        ++startSearchIndex;
        while (*searchStartPtr != '\0' && tempPtr) {
            tempPtr = tempPtr->children[*searchStartPtr - 'a'];
            if (tempPtr && tempPtr->str) {
                // found a valid word/permutation and candidate for next search
                nextSearch.push(startSearchIndex);
            }
            ++startSearchIndex;
            ++searchStartPtr;
        }
     
        if (*searchStartPtr == '\0' && tempPtr && tempPtr->str) {
            return true;
        }
    }

    return false;
}

// ********************************************************************************

// Test

// ********************************************************************************

void Test_PermutationDetector()

{

    PermutationDetector detector({"actor", "bad", "act", "good"});

    assert(detector.IsPermutation("badactorgoodacting") == false);

    assert(detector.IsPermutation_R("badactorgoodacting") == false);

    detector.ConstructDict({"actor", "bad", "acting", "good"}, false);

    assert(detector.IsPermutation("badactorgoodacting") == true);

    assert(detector.IsPermutation_R("badactorgoodacting") == true);

}