华为OD机试真题---字符串化繁为简

华为OD机试真题中的“字符串化繁为简”题目是一个涉及字符串处理和等效关系传递的问题。以下是对该题目的详细解析：

一、题目描述

给定一个输入字符串，字符串只可能由英文字母（a~z、A~Z）和左右小括号（(、)）组成。当字符里存在小括号时，小括号是成对的，可以有一个或多个小括号对，小括号对不会嵌套，小括号对内可以包含1个或多个英文字母也可以不包含英文字母。要求对这个输入字符串做简化，输出一个新的字符串，满足以下条件：

1. 输出字符串里只需保留输入字符串里的没有被小括号对包含的字符（按照输入字符串里的字符顺序）。

2. 将每个字符替换为在小括号对里包含的字典序最小的等效字符。等效关系定义如下：

   • 当小括号对内包含多个英文字母时，这些字母之间是相互等效的关系。
   • 等效关系可以在不同的小括号对之间传递，即当存在a和b等效和存在b和c等效时，a和c也等效。
   • 同一个英文字母的大写字母和小写字母也相互等效（即使它们分布在不同的括号对里）。

如果简化后的字符串为空，则输出为“0”。

二、示例

1. 示例1：

   • 输入：()abd
   • 输出：abd
   • 说明：输入字符串里没有被小括号包含的字符串为"abd"，其中每个字符没有等效字符，输出为"abd"。

2. 示例2：

   • 输入：(abd)demand(fb)()for
   • 输出：aemanaaor
   • aabebmnor。
   • 说明：等效字符集为(a,b,d,f)，输入字符串里没有被小括号包含的字符串集合为"demandfor"，将其中字符替换为字典序最小的等效字符后输出为：“aemanaaor”。

3. 示例3：

   • 输入：happy(xyz)new(wxy)year(t)
   • 输出：happwnewwear
   • 说明：等效字符集为(w,x,y,z)，输入字符串里没有被小括号包含的字符串集合为"happynewyear"，将其中字符替换为字典序最小的等效字符后输出为：“happwnewwear”。

三、解题思路

1. 提取等效字符：

   • 遍历输入字符串，使用栈（stack）来识别和处理小括号对。
   • 当遇到左括号"("时，将其位置压入栈中。
   • 当遇到右括号")"时，弹出栈顶的左括号位置，并计算这对括号之间的字符作为等效字符集合。
   • 将这些等效字符转换为小写（或大写，以保持一致性），并放入一个集合（set）中去重。

2. 构建等效关系：

   • 使用并查集（Union Find）数据结构来维护等效关系。
   • 遍历等效字符集合，将每个字符与其等效的字符合并到同一个集合中。

3. 替换字符：

   • 遍历输入字符串中未被小括号包含的字符部分。
   • 对于每个字符，检查它是否属于某个等效字符集合。
   • 如果是，则将其替换为该集合中字典序最小的字符。

4. 输出结果：

   • 将替换后的字符按照原顺序拼接成新的字符串。
   • 如果新字符串为空，则输出"0"。

四、代码实现

import java.util.Collections;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;public class StringSimplification {/*** 主函数入口* 该函数提示用户输入一个字符串，然后调用simplifyString方法处理该字符串* 需要处理输入流的异常，确保程序的健壮性* @param args 命令行参数，未使用*/public static void main(String[] args) {try (Scanner scanner = new Scanner(System.in)) {// 提示用户输入字符串System.out.print("请输入字符串: ");String input = scanner.nextLine();// 输入验证if (input == null || input.trim().isEmpty()) {System.out.println("输入不能为空");return;}// 调用方法处理输入的字符串，并打印结果String result = simplifyString(input);System.out.println(result);} catch (InputMismatchException ime) {// 处理输入格式错误异常System.err.println("输入格式错误: " + ime.getMessage());} catch (NoSuchElementException nse) {// 处理输入流结束异常System.err.println("输入流已结束，请确保在提示后输入字符串: " + nse.getMessage());} catch (Exception e) {// 处理其他异常System.err.println("发生错误: " + e.getMessage());e.printStackTrace(); // 打印堆栈跟踪}}/*** 简化给定的字符串，通过等效字符替换和括号规则* * @param input 待简化的输入字符串，包含字母和括号* @return 简化后的字符串，其中等效字符被替换为字典序最小的字符，且不包含括号* @throws IllegalArgumentException 如果括号不匹配，则抛出此异常*/public static String simplifyString(String input) {// 使用并查集来维护等效关系UnionFind uf = new UnionFind(26 * 2); // 26个小写字母和26个大写字母// 用于存储等效字符集合Set<Character> currentSet = new HashSet<>();// 用于处理括号匹配Stack<Integer> parenthesisStack = new Stack<>();// 用于构建未被括号包含的字符序列StringBuilder newStr = new StringBuilder();// 遍历输入字符串for (int i = 0; i < input.length(); i++) {char c = input.charAt(i);if (c == '(') {// 遇到左括号，压入栈中parenthesisStack.push(i);currentSet.clear();System.out.println("遇到左括号，当前索引: " + i);} else if (c == ')') {// 遇到右括号，处理等效字符集合if (parenthesisStack.isEmpty()) {throw new IllegalArgumentException("括号不匹配");}int startIndex = parenthesisStack.pop();// 检查括号内是否有字符if (startIndex + 1 < i) {StringBuilder sb = new StringBuilder(input.substring(startIndex + 1, i));// 将等效字符转换为小写并去重for (char ch : sb.toString().toCharArray()) {ch = Character.toLowerCase(ch);currentSet.add(ch);}// 维护等效关系if (!currentSet.isEmpty()) {char minChar = Collections.min(currentSet);for (char ch : currentSet) {if (Character.isLowerCase(ch)) {uf.union(ch - 'a', minChar - 'a');} else if (Character.isUpperCase(ch)) {uf.union(ch - 'A' + 26, minChar - 'a' + 26);}}currentSet.clear();}}} else {// 非括号字符，添加到 newStr 中newStr.append(c);System.out.println("添加非括号字符: " + c);}}// 检查是否有未匹配的左括号if (!parenthesisStack.isEmpty()) {throw new IllegalArgumentException("括号不匹配");}// 替换 newStr 中的字符为等效字符集合中的最小字符StringBuilder simplifiedStr = new StringBuilder();for (char c : newStr.toString().toCharArray()) {char lowerC = Character.toLowerCase(c);int root = uf.find(lowerC - 'a'); // 查找等效字符集合的根节点（最小字符）char minEquivChar = (char)('a' + root);simplifiedStr.append(minEquivChar);System.out.println("替换字符: " + c + " -> " + minEquivChar);}// 如果简化后的字符串为空，则返回 "0"return simplifiedStr.length() == 0 ? "0" : simplifiedStr.toString();}// 并查集数据结构static class UnionFind {private int[] parent;public UnionFind(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩，将x的父节点直接指向根节点}return parent[x];}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY; // 将x的根节点指向y的根节点}}}
}

五、注意事项

1. 处理大小写：在构建等效关系和替换字符时，需要注意大小写字母之间的等效关系。可以将所有字符转换为小写（或大写）来处理。
2. 边界条件：注意处理输入字符串为空或只包含括号等特殊情况。
3. 性能优化：使用并查集数据结构来高效地维护等效关系，避免使用复杂的嵌套循环或递归结构。

通过上述解析和代码实现，可以有效地解决华为OD机试中的“字符串化繁为简”问题。