Skip to content

3481. Apply Substitutions 👍

  • Time: $O(|\texttt{text}|^2)$
  • Space: $O(|\texttt{replacements}| + |\texttt{text}|)$
 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
class Solution {
 public:
  string applySubstitutions(vector<vector<string>>& replacements, string text) {
    unordered_map<string, string> replaceMap;

    for (const vector<string>& replacement : replacements) {
      const string& key = replacement[0];
      const string& value = replacement[1];
      replaceMap[key] = value;
    }

    return evaluate(text, replaceMap);
  }

 private:
  // Evaluates the `text` and replaces the placeholders with the values
  // from the `replaceMap` recursively.
  string evaluate(const string& text,
                  const unordered_map<string, string>& replaceMap) {
    string res;
    int i = 0;
    while (i < text.length())
      if (text[i] == '%') {
        const int j = i + 1 + text.substr(i + 1).find('%');
        const string key = text.substr(i + 1, j - i - 1);
        const string value = replaceMap.at(key);
        res += evaluate(value, replaceMap);
        i = j + 1;
      } else {
        res += text[i++];
      }
    return res;
  }
};

 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
class Solution {
  public String applySubstitutions(List<List<String>> replacements, String text) {
    Map<String, String> replaceMap = new HashMap<>();

    for (List<String> replacement : replacements) {
      final String key = replacement.get(0);
      final String value = replacement.get(1);
      replaceMap.put(key, value);
    }

    return evaluate(text, replaceMap);
  }

  // Evaluates the `text` and replaces the placeholders with the values
  // from the `replaceMap` recursively.
  private String evaluate(final String text, Map<String, String> replaceMap) {
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < text.length())
      if (text.charAt(i) == '%') {
        final int j = i + 1 + text.substring(i + 1).indexOf('%');
        final String key = text.substring(i + 1, j);
        final String value = replaceMap.get(key);
        sb.append(evaluate(value, replaceMap));
        i = j + 1;
      } else {
        sb.append(text.charAt(i++));
      }
    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def applySubstitutions(self, replacements: list[list[str]], text: str) -> str:
    replaceMap = {key: value for key, value in replacements}

    def evaluate(text: str) -> str:
      """
      Evaluates the text and replaces the placeholders with the values
      from the replace_map recursively.
      """
      res = []
      i = 0
      while i < len(text):
        if text[i] == '%':
          j = i + 1 + text[i + 1:].find('%')
          key = text[i + 1:j]
          value = replaceMap[key]
          res.append(evaluate(value))
          i = j + 1
        else:
          res.append(text[i])
          i += 1
      return ''.join(res)

    return evaluate(text)