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 ans
Finding 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 ans
The 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