字符串序列判定 - 华为OD统一考试(D卷)
OD统一考试(D卷)
分值: 100分
题解: Java / Python / C++
题目描述
输入两个字符串S和L,都只包含英文小写字母。S长度<=100,L长度<=500,000。判定S是否是L的有效字串。
判定规则:
- S中的每个字符在L中都能找到(可以不连续),且S在L中字符的前后顺序与S中顺序要保持一致。
- (例如,S="ace"是L="abcde”的一个子序列且有效字符是a、c、e,而”aec"不是有效子序列,且有效字符只有a、e)
输入描述
输入两个字符串S和L,都只包含英文小写字母。S长度<=100,L长度<=500,000 先输入S,再输入L,每个字符串占一行。
输出描述
S串最后一个有效字符在L中的位置。 (首位从0开始计算,无有效字符返回-1)
示例1
输入:
ace
abcde
输出:
4
示例2
输入:
fgh
abcde
输出:
-1
题解
这道题目的主要思路是遍历字符串L,在遍历的过程中,逐一比较L中的字符和S中的字符是否相等。如果相等,则S的索引前进一步,直到S的索引达到S的长度。在这个过程中,记录每次匹配成功时L中的索引位置。最后输出最后一个有效字符在L中的位置。
这种方法的时间复杂度是O(n),其中n是字符串L的长度。因为每个字符只需要遍历一次。
注意,这个题目并不要求S在L中是连续的子串,只需要保持相对顺序一致即可。
给定的代码是用Java实现的,也提供了Python和C++的实现。
在Python的代码中,使用了
input()
函数获取输入字符串。在C++的代码中,使用了
cin
来获取输入。这些代码的基本逻辑是相同的,只是语法上有些差异。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine(), t = sc.nextLine();
int n1 = s.length(), n2 = t.length();
int
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
华为OD机考(C卷、D卷)题库(绝对都是原题,命中率 95%以上。),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。