3481. 应用替换 🔒

题目描述

给定一个 replacements 映射和一个可能包含格式为 %var% 占位符 的字符串 text，其中每个 var 对应 replacements 中的一个键。每个替换值本身可能包含 一个或多个 此类占位符。每个 占位符 都被与其相应的替换键对应的值替换。

返回完全替换后不含任何 占位符 的 text 字符串。

示例 1：

输入：replacements = [["A","abc"],["B","def"]], text = "%A%_%B%"

输出："abc_def"

解释：

映射将 "A" 与 "abc" 关联，并将 "B" 与 "def" 关联。
用 "abc" 替换文本中的 %A%，并用 "def" 替换文本中的 %B%。
最终文本变为 "abc_def"。

示例 2：

输入：replacements = [["A","bce"],["B","ace"],["C","abc%B%"]], text = "%A%_%B%_%C%"

输出："bce_ace_abcace"

解释：

映射将 "A" 与 "bce" 关联，"B" 与 "ace" 关联，以及 "C" 与 "abc%B%" 关联。
用 "bce" 替换文本中的 %A%，并用 "ace" 替换文本中的 %B%。
接着，对于 %C%，用 "ace" 替换 "abc%B%" 中的 %B% 来得到 "abcace"。
最终文本变为 "bce_ace_abcace"。

提示：

1 <= replacements.length <= 10
replacements 中的每个元素是一个双值列表 [key, value]，其中：
- key 是一个大写英语字母。
- value 是一个最多有 8 个字符，可能包含 0 个或更多格式为 %<key>% 的占位符的非空字符串。
所有的替换键互不相同。
text 字符串是通过从替换映射中随机串联所有 key 占位符（格式为 %<key>%）而形成的，以虚线分隔。
text.length == 4 * replacements.length - 1
text 或任何替换值中的每个占位符对应 replacements 映射中的一个键。
替换键之间没有循环依赖。

解法

方法一：哈希表 + 递归

我们用一个哈希表 \(\textit{d}\) 来存储替换的映射关系，然后定义一个函数 \(\textit{dfs}\) 来递归地替换字符串中的占位符。

函数 \(\textit{dfs}\) 的执行逻辑如下：

在字符串 \(\textit{s}\) 中查找第一个占位符的起始位置 \(i\)，如果找不到，则返回 \(\textit{s}\)；
在字符串 \(\textit{s}\) 中查找第一个占位符的结束位置 \(j\)，如果找不到，则返回 \(\textit{s}\)；
截取占位符的键值 \(key\)，然后递归地替换占位符的值 \(d[key]\)；
返回替换后的字符串。

在主函数中，我们调用 \(\textit{dfs}\) 函数，传入文本字符串 \(\textit{text}\)，并返回结果。

时间复杂度 \(O(m + n \times L)\)，空间复杂度 \(O(m + n \times L)\)。其中 \(m\) 为替换映射的长度，而 \(n\) 和 \(L\) 分别为文本字符串的长度和占位符的平均长度。

Python3JavaC++GoTypeScript

class Solution:
    def applySubstitutions(self, replacements: List[List[str]], text: str) -> str:
        def dfs(s: str) -> str:
            i = s.find("%")
            if i == -1:
                return s
            j = s.find("%", i + 1)
            if j == -1:
                return s
            key = s[i + 1 : j]
            replacement = dfs(d[key])
            return s[:i] + replacement + dfs(s[j + 1 :])

        d = {s: t for s, t in replacements}
        return dfs(text)

class Solution {
    private final Map<String, String> d = new HashMap<>();

    public String applySubstitutions(List<List<String>> replacements, String text) {
        for (List<String> e : replacements) {
            d.put(e.get(0), e.get(1));
        }
        return dfs(text);
    }

    private String dfs(String s) {
        int i = s.indexOf("%");
        if (i == -1) {
            return s;
        }
        int j = s.indexOf("%", i + 1);
        if (j == -1) {
            return s;
        }
        String key = s.substring(i + 1, j);
        String replacement = dfs(d.getOrDefault(key, ""));
        return s.substring(0, i) + replacement + dfs(s.substring(j + 1));
    }
}

class Solution {
public:
    string applySubstitutions(vector<vector<string>>& replacements, string text) {
        unordered_map<string, string> d;
        for (const auto& e : replacements) {
            d[e[0]] = e[1];
        }
        auto dfs = [&](this auto&& dfs, const string& s) -> string {
            size_t i = s.find('%');
            if (i == string::npos) {
                return s;
            }
            size_t j = s.find('%', i + 1);
            if (j == string::npos) {
                return s;
            }
            string key = s.substr(i + 1, j - i - 1);
            string replacement = dfs(d[key]);
            return s.substr(0, i) + replacement + dfs(s.substr(j + 1));
        };
        return dfs(text);
    }
};

func applySubstitutions(replacements [][]string, text string) string {
    d := make(map[string]string)
    for _, e := range replacements {
        d[e[0]] = e[1]
    }
    var dfs func(string) string
    dfs = func(s string) string {
        i := strings.Index(s, "%")
        if i == -1 {
            return s
        }
        j := strings.Index(s[i+1:], "%")
        if j == -1 {
            return s
        }
        j += i + 1
        key := s[i+1 : j]
        replacement := dfs(d[key])
        return s[:i] + replacement + dfs(s[j+1:])
    }

    return dfs(text)
}

function applySubstitutions(replacements: string[][], text: string): string {
    const d: Record<string, string> = {};
    for (const [key, value] of replacements) {
        d[key] = value;
    }

    const dfs = (s: string): string => {
        const i = s.indexOf('%');
        if (i === -1) {
            return s;
        }
        const j = s.indexOf('%', i + 1);
        if (j === -1) {
            return s;
        }
        const key = s.slice(i + 1, j);
        const replacement = dfs(d[key] ?? '');
        return s.slice(0, i) + replacement + dfs(s.slice(j + 1));
    };

    return dfs(text);
}

3481. 应用替换 🔒

题目描述

解法

方法一：哈希表 + 递归

评论