Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a list of rules in the form of “A-B”, find out the original word. The original word only has unique letters.
For example, given [“B-C”, “C-D”, “A-B”], return the original word which is “ABCD”
Bruteforce Algorithm to Restore the Word from Rules
From the rules, we can find out the list of characters/letters and then we can permutate it via itertools.permutation. For each permutated word, we can check if violates any of the rules – if not, it is the result.
A full permutation takes O(N!) time, and to check if it violates one rule, first we need to locate the index that takes O(N) time, and N rules will make it 
. Overall time complexity is 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | from itertools import permutations def findWord(rules): def check(p): for rule in rules: a, b = rule.split('-') w = p.index(a) if w + 1 >= len(p) or p[w + 1] != b: return False return True letters = set() for rule in rules: a, b = rule.split('-') letters.add(a) letters.add(b) for s in permutations(letters): if check(s): return "".join(s) |
from itertools import permutations
def findWord(rules):
def check(p):
for rule in rules:
a, b = rule.split('-')
w = p.index(a)
if w + 1 >= len(p) or p[w + 1] != b:
return False
return True
letters = set()
for rule in rules:
a, b = rule.split('-')
letters.add(a)
letters.add(b)
for s in permutations(letters):
if check(s):
return "".join(s)Find the First and Follow the Path
If we can find the first character, we then can follow the path. The in-degree of the first letter is zero while the out-degree of the last characters is zero.
We use a hash map to remember the next character so that we can follow the path.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | from collections import defaultdict def findWord(rules): m = {} data = defaultdict(int) for rule in rules: a, b = rule.split("-") data[b] += 1 data[a] -= 1 m[a] = b cur = [i for i in data if data[i] < 0][0] ans = cur while cur in m: ans += m[cur] cur = m[cur] return ans |
from collections import defaultdict
def findWord(rules):
m = {}
data = defaultdict(int)
for rule in rules:
a, b = rule.split("-")
data[b] += 1
data[a] -= 1
m[a] = b
cur = [i for i in data if data[i] < 0][0]
ans = cur
while cur in m:
ans += m[cur]
cur = m[cur]
return ansFinding the first letter can also be accomplished by removing the “next” character from the set of all characters.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def findWord(rules): data = set() for rule in rules: a, b = rule.split('-') data.add(a) data.add(b) m = {} for rule in rules: a, b = rule.split('-') data.remove(b) m[a] = b cur = list(data)[0] ans = cur while cur in m: ans += m[cur] cur = m[cur] return ans |
def findWord(rules):
data = set()
for rule in rules:
a, b = rule.split('-')
data.add(a)
data.add(b)
m = {}
for rule in rules:
a, b = rule.split('-')
data.remove(b)
m[a] = b
cur = list(data)[0]
ans = cur
while cur in m:
ans += m[cur]
cur = m[cur]
return ansThe time and space complexity for both implementations are O(N) where N is the number of characters in the original word.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Best Time to Buy and Sell Stock (Buy and Sell Once - Three Algorithms)
Next Post: Teaching Kids Programming - Cousin Nodes in Binary Tree via Breadth First Search & Depth First Search Algorithm
