Teaching Kids Programming – Restore the Word from Rules

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

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.

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.

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) —