华为OD机试 C++ 【字符串替换】

末蓝、 2024-02-19 08:36 51阅读 0赞

### 描述 ###

给你一串只包含英文字母（无论大写或小写）和小括号的字符。注意，小括号总是成对出现，并且不会互相嵌套。

小括号里的英文字母表示它们之间是等价的。比如在"(ab)“里，‘a’ 和 ‘b’ 是等价的。而在”(bc)"里，‘b’ 和 ‘c’ 是等价的。因此，‘a’、‘b’、和 ‘c’ 三者都是等价的。再加上大写和小写字母本身也是等价的，这些关系会形成一个等价集合。

现在的任务是，你要返回一个新的字符串，保留原字符串中未被小括号包围的字符，并用该字符的等价集合中的最小字符来替代它。如果所有字符都被替代，那么返回"0"。

示例：

输入: “()abd”  
输出: “abd”  
解释: 没有被小括号包围的字符是"abd"，并且没有等价的字符需要替换。

输入: “(abd)demand(fb)()for”  
输出: “aemanaaor”  
解释: ‘a’、‘b’、‘d’ 和 ‘f’ 是等价的。所以用 ‘a’ 这个字符来替代它们。

输入: “()happy(xyz)new(wxy)year(t)”  
输出: “happwnewwear”  
解释: ‘x’、‘y’、‘z’ 和 ‘w’ 是等价的。所以用 ‘w’ 这个字符来替代它们。

思路  
首先从输入中分离出两类字符：括号内的（表示有关联的字符，彼此等效）和括号外的（需要替换的主体字符）。然后找出每组括号内字母中的最小字母，并使用它来替换主体字符中的等效字母。例如，如果a和b在括号内，则括号外的b会被替换成a。最后返回处理后的字符串作为输出。

### 代码 ###

#include <iostream>
    #include <vector>
    #include <set>
    #include <map>
    #include <algorithm>
    
    std::vector<std::set<char>> parseEquivalenceClasses(const std::string& s) {
        
        std::vector<std::set<char>> eqClasses;
        std::set<char> currentClass;
        bool isInside = false;
    
        for (char ch : s) {
        
            if (ch == '(') {
        
                isInside = true;
            } else if (ch == ')') {
        
                isInside = false;
                if (!currentClass.empty()) {
        
                    eqClasses.push_back(currentClass);
                    currentClass.clear();
                }
            } else if (isInside) {
        
                currentClass.insert(tolower(ch));
            }
        }
    
        return eqClasses;
    }
    
    std::vector<std::set<char>> mergeEquivalenceClasses(std::vector<std::set<char>>& eqClasses) {
        
        for (size_t i = 0; i < eqClasses.size(); ++i) {
        
            for (size_t j = i + 1; j < eqClasses.size();) {
        
                std::vector<char> intersection;
                std::set_intersection(eqClasses[i].begin(), eqClasses[i].end(),
                                      eqClasses[j].begin(), eqClasses[j].end(),
                                      std::back_inserter(intersection));
    
                if (!intersection.empty()) {
        
                    eqClasses[i].insert(eqClasses[j].begin(), eqClasses[j].end());
                    eqClasses.erase(eqClasses.begin() + j);
                } else {
        
                    ++j;
                }
            }
        }
    
        return eqClasses;
    }
    
    std::string replaceCharacters(const std::string& s, const std::map<char, char>& replacementMap) {
        
        std::string result;
    
        for (char ch : s) {
        
            if (ch != '(' && ch != ')') {
        
                auto it = replacementMap.find(tolower(ch));
                result += (it != replacementMap.end()) ? it->second : ch;
            }
        }
    
        return result.empty() ? "0" : result;
    }
    
    std::string simplifyString(const std::string& s) {
        
        auto eqClasses = parseEquivalenceClasses(s);
        eqClasses = mergeEquivalenceClasses(eqClasses);
    
        std::map<char, char> replacementMap;
        for (const auto& eqClass : eqClasses) {
        
            char minChar = *std::min_element(eqClass.begin(), eqClass.end());
            for (char ch : eqClass) {
        
                replacementMap[ch] = minChar;
            }
        }
    
        return replaceCharacters(s, replacementMap);
    }
    
    int main() {
        
        std::string input = "(abd)demand(fb)()for";
        std::cout << simplifyString(input) << std::endl;
    
        return 0;
    }