【华为OD-E卷 - 字符串解密 100分（python、java、c++、js、c）】

【华为OD-E卷 - 字符串解密 100分（python、java、c++、js、c）】

题目

给定两个字符串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”

输入描述

• input_string1 input_string2

输出描述

• output_string

用例

用例一：

输入：

123admyffc79pt
ssyy

输出：

pt

用例二：

输入：

123admyffc79ptaagghi2222smeersst88mnrt
ssyyfgh

输出：

mnrt

python解法

• 解题思路：
• 该代码旨在从字符串 s1 中提取不包含十六进制字符（0-9, a-f）的有效子字符串，并从中找到与字符串 s2 的字符集合限制匹配的最长有效子字符串。

分割字符串 s1

使用正则表达式 “[0-9a-f]+” 将字符串 s1 按照十六进制字符分割，提取出不含这些字符的子字符串。
这些子字符串可能包含重复字符或其他字符。
筛选有效子字符串

一个有效的子字符串必须满足以下条件：
子字符串中不同字符的数量不超过字符串 s2 的字符种类数。
通过 set 数据结构来判断子字符串的字符种类数量是否满足要求。
寻找符合条件的最长子字符串

在筛选出的子字符串中，按照以下规则排序并取出第一个字符串作为结果：
优先按照字符种类数量降序排列（字符种类越多越靠前）。
如果字符种类数量相同，按字典序降序排列。
返回结果

如果筛选后有符合条件的子字符串，返回最符合条件的字符串。
如果没有符合条件的子字符串，则返回 “Not Found”。

import re


def split_valid_strings(s1):
    """
    分割字符串 s1，提取不包含十六进制字符 (0-9, a-f) 的子字符串。
    """
    # 定义正则表达式匹配十六进制字符
    pattern = r"[0-9a-f]+"
    # 使用 re.split 分割字符串并返回分割结果
    return re.split(pattern, s1)


def filter_valid_strings(valid_strings, limit):
    """
    过滤有效的子字符串：
    - 排除空字符串。
    - 子字符串中字符种类数不超过 limit。
    """
    # 使用 filter 和 lambda 表达式过滤符合条件的字符串
    return list(filter(lambda v: v != "" and len(set(v)) <= limit, valid_strings))


def find_largest_valid_string(s1, s2):
    """
    从 s1 中提取有效子字符串，筛选符合 s2 字符种类限制的最长有效字符串。
    """
    # 分割字符串 s1，获取不包含十六进制字符的子字符串
    valid_strings = split_valid_strings(s1)
    # 计算 s2 中的字符种类数，作为子字符串的字符种类限制
    limit = len(set(s2))
    # 筛选出符合字符种类限制的子字符串
    filtered_strings = filter_valid_strings(valid_strings, limit)

    # 如果有符合条件的子字符串，则找出最长的子字符串
    if filtered_strings:
        # 按以下规则排序：
        # 1. 字符种类数（降序）。
        # 2. 字符串字典序（降序）。
        filtered_strings.sort(key=lambda x: (-len(set(x)), [-ord(c) for c in x]))
        return filtered_strings[0]
    else:
        # 如果没有符合条件的子字符串，返回 "Not Found"
        return "Not Found"


def main():
    """
    主函数：处理输入和输出。
    """
    # 输入字符串 s1 和 s2
    s1 = input()
    s2 = input()
    # 调用主逻辑函数计算结果
    result = find_largest_valid_string(s1, s2)
    # 输出结果
    print(result)


if __name__ == "__main__":
    main()

java解法

• 解题思路
• 该代码旨在从字符串 s1 中提取出不包含十六进制字符（0-9, a-f）的子字符串，并从中找到符合字符串 s2 的字符种类限制的最长有效子字符串。

分割字符串 s1

使用正则表达式 “[0-9a-f]+” 将字符串 s1 按照十六进制字符分割，提取出不含这些字符的子字符串。
结果存储在 validParts 数组中。
计算 s2 的字符种类

遍历 s2 中的所有字符，统计唯一字符的数量，作为字符种类限制 targetCount。
使用一个 HashSet 来存储字符，从而快速计算唯一字符数量。
筛选符合条件的子字符串

遍历 validParts 中的每个子字符串：
如果子字符串为空，则跳过。
计算子字符串中的唯一字符数量 uniqueInPart。
如果 uniqueInPart 不超过 targetCount：
检查是否比当前结果更优：
如果 uniqueInPart 更大，则更新结果。
如果 uniqueInPart 相同，则按字典序比较，选择较大的字符串。
返回结果

如果有符合条件的子字符串，返回最符合条件的字符串。
如果没有符合条件的子字符串，返回 “Not Found”。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入两个字符串
        String s1 = sc.next();
        String s2 = sc.next();

        // 调用方法计算并输出结果
        System.out.println(findSub(s1, s2));
    }

    /**
     * 从字符串 s1 中找到符合 s2 字符种类限制的最长有效子字符串
     *
     * @param s1 原始字符串
     * @param s2 用于限制字符种类的字符串
     * @return 符合条件的最长子字符串，如果没有，返回 "Not Found"
     */
    public static String findSub(String s1, String s2) {
        // 分割字符串 s1，提取不包含十六进制字符的部分
        String[] validParts = s1.split("[0-9a-f]+");

        // 计算 s2 中的字符种类限制
        int targetCount = uniqueCount(s2);

        // 初始化结果
        String result = "Not Found";
        int maxUnique = 0;

        // 遍历所有有效部分
        for (String part : validParts) {
            if (!part.isEmpty()) {
                // 计算当前部分的字符种类数
                int uniqueInPart = uniqueCount(part);

                // 如果当前部分满足字符种类限制
                if (uniqueInPart <= targetCount) {
                    // 判断是否比当前结果更优
                    if (uniqueInPart > maxUnique || (uniqueInPart == maxUnique && part.compareTo(result) > 0)) {
                        result = part;
                        maxUnique = uniqueInPart; // 更新最大字符种类数
                    }
                }
            }
        }

        // 返回结果
        return result;
    }

    /**
     * 计算字符串中的唯一字符数量
     *
     * @param s 输入字符串
     * @return 唯一字符的数量
     */
    private static int uniqueCount(String s) {
        // 使用 HashSet 统计唯一字符
        Set<Character> uniqueChars = new HashSet<>();
        for (char c : s.toCharArray()) {
            uniqueChars.add(c);
        }
        return uniqueChars.size();
    }
}

C++解法

• 解题思路
• 这段代码的目标是，从输入的字符串 str1 中找到一个最长的子串，且该子串中唯一字符的数量不能超过另一个输入字符串 str2 中的唯一字符数量。如果没有满足条件的子串，返回 “Not Found”。

主要步骤：

使用正则表达式将 str1 切分为非十六进制格式的子串。
将 str2 转换为一个集合，获取其中唯一字符的数量。
遍历切分出的所有子串，筛选出唯一字符数不超过 str2 中唯一字符数的子串。
按照以下规则对筛选出的子串进行排序：
首先比较子串的唯一字符数量，数量多的优先。
如果唯一字符数量相同，长度更长的优先。
返回符合条件的最长子串；如果没有符合条件的子串，返回 “Not Found”。

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <regex>

using namespace std;

// 获取结果的函数
string getResult(const string& str1, const string& str2) {
    // 使用正则表达式匹配非16进制子串（十六进制字符包括0-9和a-f）
    regex pattern("[0-9a-f]+");
    // 使用正则表达式分割字符串，获取非16进制的子串
    sregex_token_iterator it(str1.begin(), str1.end(), pattern, -1);
    sregex_token_iterator end;

    // 计算str2中字符的唯一数量，将其存入集合以去重
    set<char> str2Set(str2.begin(), str2.end());
    int count = str2Set.size();

    // 保存符合条件的子串
    vector<string> valids;
    while (it != end) {
        string valid = *it; // 获取当前子串
        // 计算子串中唯一字符的集合
        set<char> validSet(valid.begin(), valid.end());
        // 如果子串不为空且唯一字符数量不超过str2的唯一字符数量，则加入结果列表
        if (!valid.empty() && validSet.size() <= count) {
            valids.push_back(valid);
        }
        ++it; // 继续下一个子串
    }

    // 如果存在符合条件的子串
    if (!valids.empty()) {
        // 自定义排序规则：按唯一字符数排序，若相同则按子串长度排序
        sort(valids.begin(), valids.end(), [&](const string& a, const string& b) {
            if (set<char>(a.begin(), a.end()).size() != set<char>(b.begin(), b.end()).size()) {
                return set<char>(a.begin(), a.end()).size() > set<char>(b.begin(), b.end()).size();
            }
            return a.size() > b.size();
        });
        return valids[0];  // 返回符合条件的第一个最长子串
    } else {
        return "Not Found";  // 如果没有符合条件的子串，返回Not Found
    }
}

int main() {
    // 输入字符串
    string str1, str2;
    getline(cin, str1); // 获取第一行输入
    getline(cin, str2); // 获取第二行输入

    // 调用函数计算结果并输出
    cout << getResult(str1, str2) << endl;

    return 0;
}

C解法

• 解题思路

更新中

JS解法

• 解题思路

• 目标是从字符串 str1 中找到一个最长的子串，且该子串中的唯一字符数量不能超过字符串 str2 中的唯一字符数量。如果没有满足条件的子串，则返回 “Not Found”。

具体解题步骤如下：

提取非十六进制子串：

使用正则表达式匹配 str1 中所有非十六进制字符的子串。
十六进制字符包括 0-9 和 a-f。
提取出的子串需排除空子串。
计算基准字符集：

统计字符串 str2 中的唯一字符数量，作为条件基准。
筛选有效子串：

遍历提取出的所有子串，检查其唯一字符数量是否小于或等于 str2 中的唯一字符数量。
如果符合条件，将其作为候选子串进行比较。
排序和优先级：

如果子串的唯一字符数量更高，则优先。
如果唯一字符数量相同，选择更大的字典序子串（按照字母顺序比较）。
返回结果：

如果有有效子串，返回符合条件的最长子串。
如果没有符合条件的子串，返回 “Not Found”

const readline = require("readline");

// 创建读取输入的接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let lines = [];

// 按行读取输入
rl.on("line", (line) => {
    lines.push(line); // 将每行输入存入数组
    if (lines.length === 2) {
        const str1 = lines[0]; // 第一行输入
        const str2 = lines[1]; // 第二行输入
        console.log(findLargestSubstring(str1, str2)); // 计算并输出结果
        lines = []; // 清空输入数组以便处理下一组输入
    }
});

// 查找最长有效子串的函数
function findLargestSubstring(str1, str2) {
    // 正则表达式匹配十六进制子串，分割出非十六进制子串
    const reg = /[0-9a-f]+/g;
    const validSubs = str1.split(reg).filter(Boolean); // 分割后过滤掉空字符串

    // 计算str2中唯一字符的数量，使用Set去重
    const refCount = new Set(str2).size;

    // 初始化结果变量
    let maxSub = "Not Found"; // 最终返回的最长有效子串
    let maxUniqueCount = -1; // 最大唯一字符数，用于比较

    // 遍历所有有效子串
    for (const sub of validSubs) {
        // 计算当前子串的唯一字符数量
        const uniqueCount = new Set(sub).size;

        // 判断是否满足条件并更新结果
        if (uniqueCount <= refCount && uniqueCount > maxUniqueCount) {
            // 如果唯一字符数小于基准且大于当前最大值，更新结果
            maxUniqueCount = uniqueCount;
            maxSub = sub;
        } else if (uniqueCount === maxUniqueCount && sub > maxSub) {
            // 如果唯一字符数相同，按字典序比较，取更大的子串
            maxSub = sub;
        }
    }

    // 返回最长子串或"Not Found"
    return maxSub;
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏