3481. 应用替换 🔒

English Version

题目描述

给定一个 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}$ 的执行逻辑如下：

1. 在字符串 $\textit{s}$ 中查找第一个占位符的起始位置 $i$，如果找不到，则返回 $\textit{s}$；

2. 在字符串 $\textit{s}$ 中查找第一个占位符的结束位置 $j$，如果找不到，则返回 $\textit{s}$；

3. 截取占位符的键值 $key$，然后递归地替换占位符的值 $d[key]$；

4. 返回替换后的字符串。

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

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

Python3

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)

Java

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));
    }
}

C++

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);
    }
};

Go

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

TypeScript

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);
}