题目描述与示例

题目描述

给定两个字符串，从字符串2中找出字符串1中的所有字符，去重并按照ASCII值从小到大排序。

输入字符串1：长度不超过1024

输入字符串2：长度不超过1000000

字符范围满足ASCII编码要求，按照ASCII的值由小到大排序

输入描述

bach
bbaaccedfg

输出描述

abc

输入字符串1 为给定字符串bach，输入字符串2为bbaaccedfg，从字符串2中找出字符串1的字符，去除重复的字符，并且按照ASCII值从小到大排序，得到输出的结果为abc。

字符串1中的字符h在字符串2中找不到不输出

示例一

输入

fach
bbaaccedfg

输出

acf

说明

解题思路

本题非常简单，直接使用哈希集合的特性进行判断和去重即可。

代码

Python

# 题目：2023B-找出符合要求的字符串子串
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：哈希集合
# 代码看不懂的地方，请直接在群上提问


# 输入字符串s1，并且转换为哈希集合
set1 = set(input())
# 输入字符串s2，并且转换为哈希集合
set2 = set(input())
# 遍历set2中的字符，如果位于set1，则加入答案列表
ans = [ch for ch in set2 if ch in set1]
# 对答案列表进行排序
ans.sort()
# 输出排序后的ans合并后的结果
print("".join(ans))

Java

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入字符串s1，并且转换为哈希集合
        HashSet<Character> set1 = new HashSet<>();
        String input1 = scanner.nextLine();
        for (char ch : input1.toCharArray()) {
            set1.add(ch);
        }

        // 输入字符串s2，并且转换为哈希集合
        HashSet<Character> set2 = new HashSet<>();
        String input2 = scanner.nextLine();
        for (char ch : input2.toCharArray()) {
            set2.add(ch);
        }

        // 遍历set2中的字符，如果位于set1，则加入答案列表
        StringBuilder sb = new StringBuilder();
        for (char ch : set2) {
            if (set1.contains(ch)) {
                sb.append(ch);
            }
        }

        // 对答案列表进行排序
        char[] ans = sb.toString().toCharArray();
        java.util.Arrays.sort(ans);

        // 输出排序后的ans合并后的结果
        System.out.println(new String(ans));

        scanner.close();
    }
}

C++

“`C++
#include <iostream>
#include <unordered_set>
#include <algorithm>

int main() {
// 输入字符串s1，并且转换为哈希集合
std::unordered_set<char> set1;
std::string input1;
std::cin >> input1;
for (char ch : input1) {
set1.insert(ch);
}

<pre><code>// 输入字符串s2，并且转换为哈希集合
std::unordered_set<char> set2;
std::string input2;
std::cin >> input2;
for (char ch : input2) {
set2.insert(ch);
}

// 遍历set2中的字符，如果位于set1，则加入答案列表
std::string ans;
for (char ch : set2) {
if (set1.count(ch) > 0) {
ans += ch;
}
}

// 对答案列表进行排序
std::sort(ans.begin(), ans.end());

// 输出排序后的ans合并后的结果
std::cout << ans << std::endl;

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(``NlogN``)。排序的时间复杂度。

空间复杂度：O(``N+M``)。哈希集合所占空间。

N为s1的长度，M为s2的长度。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）