华为OD机考算法题：字符串解密

目录

题目部分

解读与分析

代码实现

---

题目部分

题目	字符串解密
题目说明	给定两个字符串string1和string2。 string1是一个被加扰的字符串。string1由小写英文字母（'a'~'z'）和数字字符（'0'~'9'）组成，而加扰字符串由'0'~'9'、'a'~'f' 组成。string1里面可能包含0个或多个加扰子串，剩下可能有0个或多个有效子串，这些有效子串被加扰子串隔开。 string2是一个参考字符串，仅由小写英文字母（'a'~'z'）组成。  你需要在string1字符串里找到一个有效子串，这个有效子串要同时满足下面两个条件：    （1）这个有效子串里不同字母的数量不超过且最接近于string2里不同字母的数量，即小于或等于string2里不同字母的数量的同时且最大。    （2）这个有效子串是满足条件（1）里的所有子串（如果有多个的话）里字典序最大的一个。 如果没有找到合适条件的子串的话，请输出"Not Found"。 示例： 输入字符串string1为"thisisanewday111forme"，输入字符串string2为"good"。string1里有效子串和加扰子串分割后可表示为："thisis"+"a"+"n"+"e"+"w"+"da"+"y"+"111f"+"orm"+"e"，去除加扰子串（"a"、"e"、"da"、"111f"、"e"）后的有效子串候选为("thisis", "n", "w", "y", "orm")。输入字符串string2里不同字母的数量为3（'g'、'o'、'd'），从有效子串候选里可以找出"orm"满足要求，其不同字母的数量为3，最接近于string2不同字母的数量。
输入描述 说明	input_string1 input_string2 输入为两个字符串，第1行是题目里的string1（被加扰的字符串），第2行是题目里的string2（参考字符串）。
输出描述 说明	output_string 输出为一个字符串（有效字符串）。
补充说明	输入字符串string1的长度在1~100000之间，string2的长度在1~500之间。
------------------------------------------------------
示例
示例1
输入	123admyffc79pt ssyy
输出	pt
说明	将输入字符串1里的加扰子串"123ad"、"ffc79"去除后得到有效子串序列："my"、"pt"，其中"my"里不同字母的数量为2（有'm'和'y'两个不同字母），"pt"里不同字母的数量为2（有'p'和't'两个不同字母）；输入字符串2里不同字母的数量为2（有's'和'y'两个不同字母）。 可得到最终输出结果为"pt"，其不同字母的数量最接近于"ssyy"里不同字母的数量的同时字典序最大。
示例2
输入	123admyffc79ptaagghi2222smeersst88mnrt ssyyfgh
输出	mnrt
说明	将输入字符串1里的加扰子串"123ad"、"ffc79"、"aa"、"2222"、"ee"、"88"去除后得到有效子串序列："my"、"pt"、"gghi"、"sm"、"rsst"、"mnrt"；输入字符串2里不同字母的数量为5（有's'、'y'、'f'、'g'、'h' 5个不同字母）。 可得到最终输出结果为"mnrt"，其不同字母的数量（为4）最接近于"ssyyfgh"里不同字母的数量，其他有效子串不同字母的数量都小于"mnrt"。
示例3
输入	abcmnq rt
输出	Not Found
说明	将输入字符串1里的加扰子串"abc"去除后得到有效子串序列："mnq"；输入字符串2里不同字母的数量为2（有'r'、't'两个不同的字母）。 可得到最终的输出结果为"Not Found"，没有符合要求的有效子串，因有效子串的里不同字母的数量（为3），大于输入字符串2里的不同字母的数量。

---

解读与分析

题目解读：

本题有 2 行输入，第一行输入字符串的字符中字符的范围是 'a'~'z' 和 '0' ~ '9'，在输入字符串中，如果字符范围在 'a'~'f' 或 '0' ~ '9' 中，那么这些字符是干扰字符，可以理解为间隔符。这些间隔符把源字符串分割成了多个字符串。

第二行输入一个字符串，统计出这个字符串中出现的唯一字符串个数，设为 max，即当同一个字母出现多次时只计算一次。

从第一行分隔出的多个字符串中，过滤掉不同字母数大于 max 的字符串。在剩下的字符串中，找出不同字母数最大的字符串，如果字符串是唯一的，输出它；如果不同字母数最大的字符串存在多个，输出字典序最大的那个；如果不存在符合条件的字符串，则输出 "Not Found"。

分析与思路：

先设置 3 个变量：
1. max，整形变量。用于统计第二行输入字符串的唯一字符个数。
2. currentMax，整形变量，初始值为 0。在遍历过程中，用于统计在分隔字符串时，记录不同字母数不大于 max 的最大个数。
3. output，字符串长度，初始值为 "Not Found"。

算法如下：
1. 遍历第二行字符串中的字母，把所有字符放到一个 set 中，最后统计 set 中元素的个数，赋值给 max。
为什么要先计算 max 值呢？因为这样做可以减少统计的工作量。
先遍历第二行字符串，在计算出 max 值之后，再遍历第一行字符串时，可以直接忽略掉分隔后长度大于 max 的字符串。否则，需要先统计分隔后的所有字符串（无论长度是多少），最后还是要过滤掉长度大于 max 的字符串，多了些不必要的工作量。
2. 遍历第一行字符串中的字母，根据干扰字母（分隔符），把它分隔成若干字符串。对于遍历过程中的每个字符串，进行如下操作：
① 如果此字符串的不同字母数大于 max，则舍弃它。
② 如果此字符串的不同字母数小于 currentMax，舍弃它。
③ 如果此字符串的不同字母数大于 currentMax，把此字符串不同字母数赋值给 currentMax，并把此字符串赋值给 output。
④ 如果此字符串的不同字母数等于 currentMax，比较此字符串与 output 的字典序大小，如果此字符串的字典序较大，则更新 output 的值为此字符串。
3. 遍历完字第一行字符串后，输出 output。

此算法只需要遍历一次字符串，时间复杂度为 o(n)。在遍历过程中，仅需要 3 个临时变量，空间复杂度为 o(1)。 

---

代码实现

Java代码

import java.util.Scanner;
import java.util.Set;
import java.util.Arrays;
import java.util.HashSet;/*** 字符串解密* * @since 2023.09.07* @version 0.1* @author Frank**/
public class StringDecrypt {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String firstLine = sc.nextLine();String secondLine = sc.nextLine();processStringDecrypt(firstLine, secondLine);}}private static void processStringDecrypt(String firstLine, String secondLine) {int max = getUniqueCount(secondLine);int currentMax = 0;String output = "Not Found";Character[] fiterChars = { 'a', 'b', 'c', 'd', 'e', 'f', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };Set<Character> filterSet = new HashSet<Character>(Arrays.asList(fiterChars));int i = 0;while (i < firstLine.length()) {Character first = firstLine.charAt( i );if( filterSet.contains( first ) ){i ++;continue;}int leftIndex = i;int rightIndex = i; // 不包含Character iterChar = firstLine.charAt( i );while( !filterSet.contains( iterChar )){i ++;if( i >= firstLine.length() ){rightIndex = i;break;}iterChar = firstLine.charAt( i );}rightIndex = i;String subStr = firstLine.substring( leftIndex, rightIndex );int subStrUniCnt = getUniqueCount( subStr );if( subStrUniCnt == 0 || subStrUniCnt < currentMax || subStrUniCnt > max  ){continue;}if( subStrUniCnt > currentMax ){currentMax = subStrUniCnt;output = subStr;continue;}// subStrLength == currentMaxif( output.compareTo( subStr ) < 0 ){output = subStr;continue;}}System.out.println(output);}private static int getUniqueCount(String secondLine) {Set<Character> charSet = new HashSet<Character>();for (int i = 0; i < secondLine.length(); i++) {charSet.add(secondLine.charAt(i));}return charSet.size();}}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var firstLine = line;var secondLine = await readline();processStringDecrypt(firstLine, secondLine);}}();function processStringDecrypt(firstLine, secondLine) {var max = getUniqueCount(secondLine);var currentMax = 0;var output = "Not Found";var filterSet = new Set(['a', 'b', 'c', 'd', 'e', 'f', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']);var i = 0;while (i < firstLine.length) {var first = firstLine.charAt(i);if (filterSet.has(first)) {i++;continue;}var leftIndex = i;var rightIndex = i; // 不包含var iterChar = firstLine.charAt(i);while (!filterSet.has(iterChar)) {i++;if (i >= firstLine.length) {rightIndex = i;break;}iterChar = firstLine.charAt(i);}rightIndex = i;var subStr = firstLine.substring(leftIndex, rightIndex);var subStrUniCnt = getUniqueCount(subStr);if (subStrUniCnt == 0 || subStrUniCnt < currentMax || subStrUniCnt > max) {continue;}if (subStrUniCnt > currentMax) {currentMax = subStrUniCnt;output = subStr;continue;}// subStrLength == currentMaxif (output < subStr) {output = subStr;continue;}}console.log(output);
}function getUniqueCount(secondLine) {var charSet = new Set();for (var i = 0; i < secondLine.length; i++) {charSet.add(secondLine.charAt(i));}return charSet.size;
}

(完)