2561. Rearranging Fruits

Posted on Edited on In

3481. Apply Substitutions

Description

You are given a replacements mapping and a text string that may contain placeholders formatted as %var%, where each var corresponds to a key in the replacements mapping. Each replacement value may itself contain one or more such placeholders . Each placeholder is replaced by the value associated with its corresponding replacement key.

Return the fully substituted text string which does not contain any placeholders .

Example 1:

1
2
3
Input: replacements = [["A","abc"],["B","def"]], text = "%A%_%B%"

Output: "abc_def"

Explanation:

  • The mapping associates "A" with "abc" and "B" with "def".
  • Replace %A% with "abc" and %B% with "def" in the text.
  • The final text becomes "abc_def".

Example 2:

1
2
3
Input: replacements = [["A","bce"],["B","ace"],["C","abc%B%"]], text = "%A%_%B%_%C%"

Output: "bce_ace_abcace"

Explanation:

  • The mapping associates "A" with "bce", "B" with "ace", and "C" with "abc%B%".
  • Replace %A% with "bce" and %B% with "ace" in the text.
  • Then, for %C%, substitute %B% in "abc%B%" with "ace" to obtain "abcace".
  • The final text becomes "bce_ace_abcace".

Constraints:

  • 1 <= replacements.length <= 10
  • Each element of replacements is a two-element list [key, value], where:
    • key is a single uppercase English letter.
    • value is a non-empty string of at most 8 characters that may contain zero or more placeholders formatted as %%.
  • All replacement keys are unique.
  • The text string is formed by concatenating all key placeholders (formatted as %%) randomly from the replacements mapping, separated by underscores.
  • text.length == 4 * replacements.length - 1
  • Every placeholder in the text or in any replacement value corresponds to a key in the replacements mapping.
  • There are no cyclic dependencies between replacement keys.

Hints/Notes

  • 2025/04/26 Q2
  • dfs
  • No solution fromm 0x3F or Leetcode

Solution

Language: C++

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
class Solution {
public:
    string applySubstitutions(vector<vector<string>>& replacements, string text) {
        unordered_map<string, string> mapping;
        for (auto& replacement : replacements) {
            string key = replacement[0], val = replacement[1];
            mapping[key] = val;
        }
        for (auto [key, val] : mapping) {
            if (val.find('%') != string::npos) {
                string res = replace(val, mapping);
                mapping[key] = res;
            }
        }
        string res = replace(text, mapping);
        return res;
    }

    string replace(string text, unordered_map<string, string>& mapping) {
        int n = text.size();
        string res;
        for (int i = 0; i < n; i++) {
            if (text[i] != '%') {
                res.push_back(text[i]);
            } else {
                int start = ++i;
                while (text[i] != '%') {
                    i++;
                }
                string key = text.substr(start, i - start);
                string next_val = mapping[key];
                while (next_val.find('%') != string::npos) {
                    string next_res = replace(next_val, mapping);
                    mapping[next_val] = next_res;
                    next_val = mapping[next_val];
                }
                res += next_val;
            }
        }
        return res;
    }
};