LeetCode 筆記 - 3481. Apply Substitutions

Posted on

題目在此 3481. Apply Substitutions

給定一個字串 text 與替換規則 replacements ，其中 $replacements[i] = [source_i, target_i]$。
請你將 text 中所有出現 $source_i$ 的地方替換成 $target_i$。替換規則會依照 replacements 陣列的順序進行，且不會有重疊的替換規則。

解題思維

這題的關鍵是做出一個相依圖，讓我們可以用 $O(1)$ 的時間複雜度找到替換規則。
一但在替換規則中找到 %x%，我們就可以用遞迴的方式繼續往下找，直到找不到 %x% 為止。

Time complexity 是 $O(r^2 * t)$，其中 r 是替換規則的數量，最多遞迴 r 次，所以是 $O(r^2 * t)$。
Space complexity 是 $O(r^2 * t)$，因為我們需要存儲替換完成的字串。

程式碼

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
class Solution:
    def applySubstitutions(self, replacements: List[List[str]], text: str) -> str:

        # step 0: create the replacement dict, let the key search time complexity from O(n) to O(1)
        # step 1: walk the text, if text[i] == '%', we replace %{text[i + 1]}% with replacement dict[text[i + 1]]
        # step 2: if '%' in replacement dict[text[i + 1]], we let replacement dict[text[i + 1]] as new text, do step 1 and 2

        # the size of replacements: 
        # the size of text: t
        # time complexity: O(r^2 * t)
        # space comlexity: O(r^2 * t)

        replaceDict = {}
        for k, v in replacements:
            replaceDict[k] = v

        def parse(text):

            result = []
            i = 0
            while i < len(text):

                if text[i] != '%':
                    result.append(text[i])
                    i += 1
                else:
                    if '%' in replaceDict[text[i + 1]]:
                        replaceDict[text[i + 1]] = parse(replaceDict[text[i + 1]])

                    result.append(replaceDict[text[i + 1]])
                    i += 3

            return ''.join(result)

        return parse(text)
                    

        
        # step 0: we walk the replacements
        # step 1: check every replacement is in text or not
        #         if replacement in text: text = text.replace(replacement[0], replacement[1])
        #         need_rerun = need_rerun or '%' in replacement[1]
        # step 2: run until need_rerun is False
        # step 3: return text

        # rerun time: R
        # the size of replacements: r
        # the size of text: t
        # time complexity: O(r^2 * t)

        # space complexity: O(t^2 * t)

        need_run = True

        skip = set()

        while need_run:
            need_run = False

            for replace, replace_with in replacements:
                if replace in skip:
                    continue

                if (target := f'%{replace}%') in text:
                    text = text.replace(target, replace_with)

                    if r'%' in replace_with:
                        need_run = True

        return text

也許你也會想看看