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 Python post - Data Structure and Algorithm - Trie.
Pseudo-code and C++ implementation please refer to my C++ post, Data Structure and Algorithm - Detect Word Permutation.

3. Python Implementation
    - Python 2.7
    - Microsoft Visual Studio Community 2015
# ********************************************************************************
# Implementation
# ********************************************************************************
# PermutationDetector.py
from DictionaryTrie import DictionaryTrie

import sys

class PermutationDetector(object):
    """Word Permutation detector"""

    def __init__(self):
        self.m_DictRoot = None

    def __init__(self, words = None):
        self.m_DictRoot = None
        self.ConstructDict(words)

    def ConstructDict(self, words = None, appendMode = False):
        try:
            if words is None:
                return
           
            if self.m_DictRoot is None or appendMode:
                self.m_DictRoot = DictionaryTrie()
       
            for word in words:
                self.m_DictRoot.AddWord(word)
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected Error: ", sys.exc_info()[0])

    # non-recursive implementation
    def IsPermutation(self, word = None):
        try:
            if word is None or self.m_DictRoot is None:
                return False
            if len(word) == 0:
                return False

            nextToSearch = [0]
            StrSize = len(word)
            while (len(nextToSearch) > 0):
                # pop first or last (queue/stack) as breadth/depth-first search
                startSearchIndex = nextToSearch.pop(0)
                tempDict = self.m_DictRoot
                idx = 0
                for idx in range(startSearchIndex, StrSize):
                    startSearchIndex +=1
                    tempDict = tempDict.GetChildren()[ord(word[idx])]
                    if tempDict is None:
                        break
                    else :
                        if tempDict.GetValue() is not None:
                            # find a valid word/permutation in trie, push index for next search
                            nextToSearch.append(startSearchIndex)

                if idx == (StrSize - 1) \
                   and tempDict is not None \
                   and tempDict.GetValue() is not None:
                    return True
        except AttributeError as e:
            print ("AtrrinuteError: {0}". format(e))
        except:
            print ("Unexpected Erro: ", sys.exc_info()[0])
        return False

    def __IsPermutation_R(self, word = None, nextToSearch = None):
        try:
            if word is None:
                return False
            if nextToSearch is None or len(nextToSearch) == 0:
                return False
           
            tempDict = self.m_DictRoot
            # pop first or last (queue/stack) as breadth/depth-first search
            startSearchIndex = nextToSearch.pop(0)
            idx = 0
            searchedLen = 0
            for idx in range(startSearchIndex, len(word)) :
                searchedLen += 1
                tempDict = tempDict.GetChildren()[ord(word[idx])]
                if tempDict is None:
                    break;
                else:
                    if tempDict.GetValue() is not None:
                        # find a valid word/permutation in trie, push index for next search
                        nextToSearch.append(startSearchIndex + searchedLen)
               
            if idx == len(word) -1 \
               and tempDict is not None \
               and tempDict.GetValue() is not None:
                return True
           
            return self.__IsPermutation_R(word, nextToSearch)
        except AttributeError as e:
            print ("AttributeError: {0}".format(e))
        except:
            print ("Unexpected Error: ", sys.exc_info()[0])
        return False

    # recursive implementation
    def IsPermutation_R(self, word = None):
        if word is None:
            return False

        nextToSearch = [0]
        return self.__IsPermutation_R(word, nextToSearch)
                           
# ********************************************************************************
# Test
# ********************************************************************************
# Test_PermutationDetector.py    
import unittest

from PermutationDetector import PermutationDetector

class Test_PermutationDetector(unittest.TestCase):
    def test_Failure(self):
        detector = PermutationDetector(("actor", "bad", "act", "good"))
        self.assertFalse(detector.IsPermutation("badactorgoodacting"))
        self.assertFalse(detector.IsPermutation_R("badactorgoodacting"))

    def test_Success(self):
        detector = PermutationDetector(("actor", "bad", "acting", "good"))
        self.assertTrue(detector.IsPermutation("badactorgoodacting"));
        self.assertTrue(detector.IsPermutation_R("badactorgoodacting"));

if __name__ == '__main__':
    unittest.main()