CTCI_python/chapter_16/p16_18.py at master · StBogdan/CTCI_python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from typing import List


def get_posib_combo(pattern_str: str, n: int) -> List[tuple]:
    ca = pattern_str.count('a')
    cb = pattern_str.count('b')

    if cb == 0:
        if n % ca != 0:
            return []
        else:
            return [(n//ca,0)]

    posibs = []
    for i in range(0, n//ca + 1):
        if (n-(ca*i)) % cb == 0:
            posibs.append((i, (n - ca*i) // cb))
    return posibs


def check_posib(text, pattern, ca, cb):
    # print(f"Checking pos {ca} and {cb}")
    a = text[:ca]
    b = None

    p_i = 1
    t_i = ca
    while p_i < len(pattern) and t_i < len(text):
        if pattern[p_i] == 'a':
            if text[t_i: t_i + ca] != a:
                # print(f"Failed at check {text[t_i: t_i + ca]} agains a: {a}")
                return False
            else:
                t_i += ca
        else:
            if not b:
                b = text[t_i: t_i + cb]
                t_i += cb
            else:
                if text[t_i: t_i + cb] != b:
                    # print(f"Failed at check {text[t_i: t_i + cb]} agains b: {b}")
                    return False
                else:
                    t_i += cb
        p_i += 1
    # print(f"Ending todays check with {p_i} of {len(pattern)} and {t_i} of {len(text)}")
    return p_i == len(pattern) and t_i == len(text)


def flip_pattern(p):
    if p[0] == 'b':
        return p.translate(str.maketrans("ab", "ba", ""))
    else:
        return p


def check_pattern_match(text: str, pattern: str) -> bool:
    pattern = flip_pattern(pattern)
    # print(f"Flipped pattern is : {pattern}")
    posibs = get_posib_combo(pattern, len(text))
    # print(f"Looking at combos pattern is : {posibs}")

    return any(check_posib(text, pattern, ca, cb) for ca, cb in posibs)


if __name__ == "__main__":
    exs = [("catcatgocatgo", "aabab"),
           ("catcatgocatgo", "bbaba"),
           ("catcatgocatgo", "b"),
           ("catcatgjocatgo", "aa"),
           ("catcatgocatgo", "ba"),
           ("catcat", "aaa"),
           ("catcat", "bb"),("a","bb")]
    for text, pattern in exs:
        print(f"'{text}' fits patterns '{pattern}'' ? {check_pattern_match(text, pattern)}")
        print("-"*50)