华为OD机试真题——字符串序列判定（2025B卷：100分）Java/python/JavaScript/C/C++/GO最佳实现

2025 B卷 100分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《字符串序列判定》：

---

文章快捷目录

题目描述及说明

Java

python

JavaScript

C++

C

GO

---

题目名称：字符串序列判定

---

知识点：字符串、双指针算法
时间限制：1秒
空间限制：256MB
限定语言：不限

---

题目描述

输入两个字符串S和L，均只包含英文小写字母。S的长度不超过100，L的长度不超过500,000。判定S是否为L的有效子串，规则如下：

1. S中的每个字符必须在L中按顺序出现（可不连续）。例如，S="ace"是L="abcde"的有效子串，而S="aec"则不是。
2. 若S是有效子串，输出其最后一个字符在L中的位置（首位从0开始计算）；否则返回-1。

输入描述
输入分为两行：

• 第一行为字符串S
• 第二行为字符串L

输出描述
一个整数，表示最后一个有效字符的位置，或-1。

示例
输入：

ace  
abcde  

输出：

4  

解释：S中的字符a、c、e在L中的位置依次为0、2、4，最后一个字符e的位置是4。

---

Java

问题分析

给定两个字符串S和L，要求判断S是否是L的有效子串，即S中的字符在L中按顺序出现（无需连续）。如果是，返回S最后一个字符在L中的位置；否则返回-1。

解题思路

使用双指针方法遍历字符串：

1. 指针i指向S的当前字符，初始为0。
2. 指针j遍历L的每个字符，寻找与S当前字符匹配的位置。
3. 记录最后一个匹配位置lastPos，当匹配到S中的所有字符时，返回lastPos。
4. 提前终止条件：若S的长度大于L，直接返回-1；若在遍历过程中S的所有字符都已匹配，立即终止循环。

代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String S = scanner.nextLine().trim(); // 读取字符串SString L = scanner.nextLine().trim(); // 读取字符串L// 如果S的长度大于L，直接返回-1if (S.length() > L.length()) {System.out.println(-1);return;}int i = 0; // 指向S当前需要匹配的字符位置int lastPos = -1; // 记录最后一个有效字符的位置for (int j = 0; j < L.length(); j++) { // 遍历L的每个字符if (i == S.length()) { // 已匹配所有字符，提前退出break;}if (L.charAt(j) == S.charAt(i)) { // 当前字符匹配i++; // 移动到S的下一个字符lastPos = j; // 更新最后一个有效位置}}// 判断是否全部匹配if (i == S.length()) {System.out.println(lastPos);} else {System.out.println(-1);}}
}

代码解析

1. 读取输入：使用Scanner读取两行输入字符串S和L，并去除前后空格。
2. 长度校验：若S的长度大于L，直接输出-1，无需后续处理。
3. 双指针遍历：
   • i初始化为0，跟踪S的匹配进度。
   • lastPos记录最后一个匹配的位置，初始为-1。
   • 遍历L的每个字符j，若当前字符匹配S的i位置字符，则i自增，并更新lastPos。
   • 当i等于S的长度时，说明所有字符已匹配，提前终止循环。
4. 结果判断：循环结束后，若i等于S的长度，输出lastPos；否则输出-1。

示例测试

示例1：
输入：

ace
abcde

输出：4
解释：S中的字符依次在位置0、2、4匹配，最后一个字符位置为4。

示例2：
输入：

aec
abcde

输出：-1
解释：无法按顺序找到所有字符，e在c之后出现，无法匹配。

示例3：
输入：

abdbc

输出：4
解释：匹配路径为a(0)、b(1)、c(4)，最后一个位置为4。

综合分析

最优性分析：

• 时间复杂度：O(n)，只需线性遍历一次L字符串，适用于L长度极大（如50万）的场景。
• 空间复杂度：O(1)，仅使用常数级变量，无额外存储消耗。

正确性保证：

• 双指针确保严格按顺序匹配，不会遗漏或错序。
• 提前终止条件减少不必要的遍历，提升效率。

适用场景：

• 适用于需要判断子序列存在性及记录位置的场景，如基因序列匹配、日志分析等。

---

python

问题分析

给定两个字符串S和L，要求判断S是否是L的有效子序列（即S中的字符