华为OD机考算法题:字符串化繁为简

目录

题目部分

解读与分析

代码实现


题目部分

题目 字符串化繁为简
题目说明 给定一个输入字符串,字符串只可能由英文字母 ('a'~'z'、'A'~'Z' )和左右小括号 ('('、')')组成。当字符里存在小括号时,小括号是成对的,可以有一个或多个小括号对,小括号对不会嵌套,小括号对内可以包含1个或多个英文字母,也可以不包含英文字母。当小括号对内包含多个英文字母时,这些字母之间是相互等效的关系,而且等效关系可以在不同的小括号对之间传递,即当存在'a'和'b'等效和存在'b'和'c' 等效时,'a' 和 'c' 也等效,另外,同一个英文字母的大写字母和小写字母也相互等效 (即使它们分布在不同的括号对里)。
需要对这个输入字符串做简化,输出一个新的字符串,输出字符串里只需保留输入字符串里的没有被小括号对包含的字符(按照输入字符串里的字符顺序) ,并将每个字符替换为在小括号对里包含且字典序最小的等效字符。
如果简化后的字符串为空,请输出为"0"。
 
示例:
输入字符串为"never(dont)give(run)up(f)()",初始等效字符集合为('d','o','n','t')、('r','u','n'),由于等效关系可以传递,因此最终等效字符集合为('d','o','n','t','r','u'),将输入字符串里的剩余部分按字典序最小的等效字符替换后得到"devedgivedp"。
输入描述 input_string
输入为 1 行,代表输入字符串。
输出描述 output_string
输出为 1 行,代表输出字符串。
补充说明 输入字符串的长度在 1 ~ 100000 之间。
-----------------------------------------------------------
示例
示例1
输入 ()abd
输出 abd
说明 输入字符串里没有被小括号包含的子字符串为"abd",其中每个字符没有等效字符,输出为"abd"。
示例2
输入 (abd)demand(fb)for
输出 aemanaaor
说明 等效字符集为('a','b','d','f'),输入字符串里没有被小括号包含的子字符串集合为 "demandfor",将其中字符替换为字典序最小的等效字符后输出为:"aemanaaor"。
示例3
输入 ()happy(xyz)new(wxy)year(t)
输出 happwnewwear
说明 等效字符集为('x','y','z','w'),输入字符串里没有被小括号包含的子字符串集合为"happynewyear",将其中字符替换为字典序最小的等效字符后输出为:"happwnewwear"。
示例4
输入 ()abcdefgAC(a)(Ab)(C)
输出 AAcdefgAC
说明 等效字符集为('a','A','b'),输入字符里没有被小括号包含的子字符串集合为"abcdefgAC",将其中字符替换为字典序最小的等效字符后输出为:"AAcdefgAC"。


解读与分析

题目解读

本题的输入和输出都是一段字符串。输出字符串在输入字符串的基础上进行精简,精简按要求如下:

1. 忽略输入字符串中所有使用小括号包裹起来的子字符串;
例如,如果输入字符串为 abc(xxx)def(xxxx),那么先去掉括号的部分,把字符串转换成中间字符串 abcdef,再进行后续操作。
2. 对于所有小括号对中所包含的字符,构建等效字符集(构建等效字符集的规则参见“分析与思路”部分)。一个字符集中所有的字符等效某个字母,这个字母是字符集中字典序最小的那个字母。
例如,某个有效字符集是 {'A', 'a', 'b'},在这个字符集的 3 个字母中,字典序最小的字母是 'A',所以当碰到这 3 个字母中任意一个时,一律转换成 'A'。

需要注意两点:
1. 输入字符串中的等效字符集可能有多个。
2. 相同英文字母的大写和小写视作等效字符。

分析与思路

设源输入的字符串为 sourceStr,接下来字符串精简可以分两步实现:

1.  遍历 sourceStr,在遍历过程中,进行如下操作。
 ①  去掉 sourceStr 中括号对包含的部分,生成中间字符串 tmpStr。
 ② 
构建等效字符集(具体算法稍后说明),并算出每个字符集等效的字母(即等效字符集中字典序最小的那个字母)。创建一个map,命名为 charSetMap,在遍历 sourceStr 过程中用于建立字符(key)和其所在的字符集(value)之间的关系。

2. 遍历完 sourceStr,构建好字符集后,进行如下操作。
 ①  创建一个 map,命名为 setTarCharMap,用于存储字符集(key)和其等效的字母(value)之间的关系。  
 ②  创建一个 map,命名为 charSrcTarMap,在 charSetMap 和 setTarCharMap 基础上,建立需要转换的字符(key)和最终转换的字符(value)之间的关系。  

 3. 遍历中间字符串 tmpStr,设最终字符串为 tarStr。遍历字符时,判断此字符是否在charSrcTarMap中存在key,如存在则替换成这个 key 所对应的 value,加到 tarStr 的末尾,否则原封不动地加到 tarStr 末尾。

最终, tarStr 的结果为精简后的字符串。

-----------------------------------------------------------

在以上的实现中,第 1 步中的关键步骤 构建等效字符集 写得比较粗略,下面详解构建等效字符集的步骤:

1. 创建一个 map,命名为 charSetMap,其 key 为等效字符集中的字符,value 为字符 set,用于存储 key 所在的结合。
举例说明,如果存在 2 个等效字符集{'a', 'b', 'c'},{'d', 'e'},那么 charSetMap 有 5 个 key,分别为 'a'、'b'、'c'、'd'、'e'。其中,'a'、'b'、'c' 这 3 个 key 所对应的 value 为 set{'a', 'b', 'c'},另外 2 个 key 对应的 value 为 set {'d','e'}。

2. 遍历字符串 srcStr,每碰到一个括号对时,提取出括号对中的所有字符,放到数组 tmpCharArr 中。遍历 tmpCharArr,检查 tmpCharArr 中的字符是否是 charSetMap 的key, 如果
 ①  tmpCharArr 中所有的字符都不是 charSetMap 的 key,则意味着 tmpCharArr 中的所有字符与已存在的等效字符集不存在交集,那么构建一个 set,设为 tmpSet,tmpSet 中包含 tmpCharArr 的所有字符。遍历 tmpCharArr,把 tmpCharArr 的元素作为 key 添加到 charSetMap,其对应的 value 为刚创建的 tmpSet。
 ② tmpCharArr 中至少有一个字符是 charSetMap 的 key,此时可能存在等效字符集合并的情况。
 · 遍历 tmpCharArr 时,当碰到第一个字符(假设为 tmpChar)是 charSetMap 的 key 时,设 set1 为 charSetMap.get( tmpChar )。
 · 继续遍历 tmpCharArr,如果下一个字符(假设为 char2)不是 charSetMap 的 key,那么把 char2 添加到 set1 中,并把 ( char2, set1) 添加到 charSetMap 中。
 · 继续遍历 tmpCharArr,如果下一个字符(假设为 char3)是 charSetMap 的 key,并且 charSetMap.get( char3) == set1,则意味着 char3 已经在 set1 中,跳过。
 · 继续遍历 tmpCharArr,如果下一个字符(假设为 char4)是 charSetMap 的 key,并且 charSetMap.get( char4) != set1,设 set2 = charSetMap.get( char4 ),则需要把 set2 合并到 set1 中。把 set2 中所有的元素添加到 set1 中,并把 set2 中所有字符作为 key 添加到 charSetMap 中,它们对应的 value 为 set2。

遍历完字符串 srcStr 之后,等效字符集构建完毕。

此算法需要遍历 2 次字符串,其时间复杂度为 o(n),由于字母个数有限,创建的各种 map 包含的元素都很有限,额外的辅助空间与字符串长度无关,空间复杂度为 o(1)。 


代码实现

Java代码

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * 字符串化繁为简
 * 
 * @since 2023.09.06
 * @version 0.1
 * @author Frank
 */
public class StringSimplify {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		// 第一行输入一串数字,以空格分隔
		String sourceStr = sc.nextLine();

		StringBuffer sb = new StringBuffer();
		// 第一次遍历 sourceStr
		int i = 0;
		Map<Character, Set<Character>> charSetMap = new HashMap<Character, Set<Character>>();
		while (i < sourceStr.length()) {
			int leftPT = sourceStr.indexOf('(', i);
			int rightPT = sourceStr.indexOf(')', i);
			// 没有小括号了
			if (leftPT == -1 && rightPT == -1) {
				sb.append(sourceStr.substring(i));
				break;
			}

			// 把 i 和 左括号之间部分加到sb。
			sb.append(sourceStr.substring(i, leftPT));

			String setStr = sourceStr.substring(leftPT + 1, rightPT);

			if (setStr.length() > 0) {
				// 构建 charSetMap
				constructCharSetMap(charSetMap, setStr);
			}

			i = rightPT + 1;
		}

		Map<Set<Character>, Character> setTarCharMap = new HashMap<Set<Character>, Character>();
		constructSetTarCharMap(charSetMap, setTarCharMap);

		Map<Character, Character> charSrcTarMap = new HashMap<Character, Character>();
		constructCharSrcTarMap(charSetMap, setTarCharMap, charSrcTarMap);

		String ret = getReplacedString(charSrcTarMap, sb.toString());
        if( ret.length() == 0 )
		{
			ret = "0";
		}
		System.out.println(ret);
	}

	private static String getReplacedString(Map<Character, Character> charSrcTarMap, String tmpStr) {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < tmpStr.length(); i++) {
			Character curChar = tmpStr.charAt(i);
			Character tarChar = charSrcTarMap.get(curChar);
			if (tarChar != null) {
				sb.append(tarChar);
			} else {
				sb.append(curChar);
			}
		}
		return sb.toString();
	}

	private static void constructCharSrcTarMap(Map<Character, Set<Character>> map,
			Map<Set<Character>, Character> setTarCharMap, Map<Character, Character> charSrcTarMap) {
		map.forEach((key, value) -> {
			Set<Character> tmpValue = map.get(key);
			Character finalValue = setTarCharMap.get(tmpValue);
			charSrcTarMap.put(key, finalValue);
		});
	}

	private static Set<Character> getValueByIgnoreKey(Map<Character, Set<Character>> map, Character key) {
		Set<Character> ret = map.get(key);
		if (ret != null) {
			return ret;
		}
		Character newKey;
		if (Character.isLowerCase(key)) {
			newKey = Character.toUpperCase(key);
		} else {
			newKey = Character.toLowerCase(key);
		}
		return map.get(newKey);
	}

	private static void constructSetTarCharMap(Map<Character, Set<Character>> map,
			Map<Set<Character>, Character> setTarCharMap) {
		Collection<Set<Character>> allSets = map.values();
		for (Iterator<Set<Character>> iter = allSets.iterator(); iter.hasNext();) {
			Set<Character> curSet = iter.next();
			Character firstChar = getSetFirstChar(curSet);
			setTarCharMap.put(curSet, firstChar);
		}
	}

	private static Character getSetFirstChar(Set<Character> curSet) {
		Character ret = null;
		for (Iterator<Character> iter = curSet.iterator(); iter.hasNext();) {
			Character curChar = iter.next();
			if (ret == null) {
				ret = curChar;
			} else if (curChar < ret) {
				ret = curChar;
			}
		}

		return ret;
	}

	private static void constructCharSetMap(Map<Character, Set<Character>> map, String setStr) {
		int inMapCnt = 0;
		Set<Character> set1 = null;

		for (int i = 0; i < setStr.length(); i++) {
			Character curChar = setStr.charAt(i);
			if (getValueByIgnoreKey(map, curChar) != null) {
				inMapCnt++;
				if (inMapCnt == 1) {
					set1 = getValueByIgnoreKey(map, curChar);
				}
			}
		}

		if (inMapCnt == 0 || inMapCnt == 1) {
			// 全都不在map中,则新建一个 set,并放到map中。
			// inMapCnt == 1, 放到初始化的 set1中。
			if (inMapCnt == 0) {
				set1 = new HashSet<Character>();
			}

			for (int i = 0; i < setStr.length(); i++) {
				Character curChar = setStr.charAt(i);
				set1.add(curChar);
				map.put(curChar, set1);
			}
			return;
		}

		// inMapCnt >= 2的情况,所有的值都合并到 set1 中。
		for (int i = 0; i < setStr.length(); i++) {
			Character curChar = setStr.charAt(i);
			set1.add(curChar);
			Set<Character> set2 = getValueByIgnoreKey(map, curChar);
			if (set2 == null) {
				map.put(curChar, set1);
				continue;
			} else if (set1 == set2) {
				continue;
			}

			// 把 set2 合并到 set1 中
			for (Iterator<Character> iter = set2.iterator(); iter.hasNext();) {
				Character charInSet2 = iter.next();
				set1.add(charInSet2);
				map.put(charInSet2, set1);
			}
		}
	}
}

这题的逻辑处理并不复杂,但代码量有些多,近 170 行,耗费了整整 1 个小时。如果是在考试中,我未必有足够的时间完成它。

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
    let input = [];
    while (line = await readline()) {
        input.push(line);
    }

    var sourceStr = input[0];
    var output = "";
    // 第一次遍历 sourceStr
    var i = 0;
    var charSetMap = new Map();
    while (i < sourceStr.length) {
        var leftPT = sourceStr.indexOf('(', i);
        var rightPT = sourceStr.indexOf(')', i);
        // 没有小括号了
        if (leftPT == -1 && rightPT == -1) {
            output += sourceStr.substring(i);
            break;
        }

        // 把 i 和 左括号之间部分加到sb。
        output += sourceStr.substring(i, leftPT);

        var setStr = sourceStr.substring(leftPT + 1, rightPT);

        if (setStr.length > 0) {
            // 构建 charSetMap
            constructCharSetMap(charSetMap, setStr);
        }

        i = rightPT + 1;
    }

    var setTarCharMap = new Map();
    constructSetTarCharMap(charSetMap, setTarCharMap);

    var charSrcTarMap = new Map();
    constructCharSrcTarMap(charSetMap, setTarCharMap, charSrcTarMap);

    var ret = getReplacedString(charSrcTarMap, output);
    if( ret.length == 0 )
    {
        ret = "0";
    }
    console.log(ret);


    function getReplacedString(charSrcTarMap, tmpStr) {
        var sb = "";
        for (var i = 0; i < tmpStr.length; i++) {
            var curChar = tmpStr.charAt(i);
            var tarChar = charSrcTarMap.get(curChar);
            if (tarChar != null) {
                sb += tarChar;
            } else {
                sb += curChar;
            }
        }
        return sb;
    }

    function constructCharSrcTarMap(map, setTarCharMap, charSrcTarMap) {
        map.forEach(function(value, key, thisMap) {
            var finalValue = setTarCharMap.get(value);
            charSrcTarMap.set(key, finalValue);
        });
    }

    function getValueByIgnoreKey(map, key) {
        var ret = map.get(key);
        if (ret != null) {
            return ret;
        }
        var newKeyCode;
        if (key >= 'a' && key <= 'z') {
            // 小写字母转换成大写
            newKeyCode = 'A'.charCodeAt() + (key.charCodeAt() - 'a'.charCodeAt());
        } else {
            newKeyCode = 'a'.charCodeAt() + (key.charCodeAt() - 'A'.charCodeAt());
        }
        return map.get(String.fromCharCode(newKeyCode));
    }

    function constructSetTarCharMap(map, setTarCharMap) {
        map.forEach(function(item) {
            var firstChar = getSetFirstChar(item);
            setTarCharMap.set(item, firstChar);
        });
    }

    function getSetFirstChar(curSet) {
        var ret = null;
        curSet.forEach(function(curChar) {
            if (ret == null) {
                ret = curChar;
            } else if (curChar < ret) {
                ret = curChar;
            }
        });
        return ret;
    }

    function constructCharSetMap(map, setStr) {
        var inMapCnt = 0;
        var set1 = null;

        for (var i = 0; i < setStr.length; i++) {
            var curChar = setStr.charAt(i);
            if (getValueByIgnoreKey(map, curChar) != null) {
                inMapCnt++;
                if (inMapCnt == 1) {
                    set1 = getValueByIgnoreKey(map, curChar);
                }
            }

        }

        if (inMapCnt == 0 || inMapCnt == 1) {
            // 全都不在map中,则新建一个 set,并放到map中。
            // inMapCnt == 1, 放到初始化的 set1中。
            if (inMapCnt == 0) {
                set1 = new Set();
            }

            for (var i = 0; i < setStr.length; i++) {
                var curChar = setStr.charAt(i);
                set1.add(curChar);
                map.set(curChar, set1);
            }
            return;
        }

        // inMapCnt >= 2的情况,所有的值都合并到 set1 中。
        for (var i = 0; i < setStr.length; i++) {
            var curChar = setStr.charAt(i);
            set1.add(curChar);
            var set2 = getValueByIgnoreKey(map, curChar);
            if (set2 == null) {
                map.set(curChar, set1);
                continue;
            } else if (set1 == set2) {
                continue;
            }

            set2.forEach(function(value) {
                set1.add(value);
                map.set(value, set1);
            })

        }

    }

}();

(完)