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
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
".
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()
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()
