最新华为OD机试真题-字符串序列判定(100分)

大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> 字符串序列判定(100分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

✨ 字符串序列判定

问题描述

输入两个字符串 和 ，都只包含英文小写字母。判定 是否是 的有效子序列。

判定规则： 中的每个字符在 中都能找到（可以不连续），且 在 中字符的前后顺序与 中顺序要保持一致。例如， 是 的一个子序列，有效字符是 、、，而 不是有效子序列。

输入格式

第一行输入字符串 ，第二行输入字符串 ，都只包含英文小写字母。

输出格式

输出 串最后一个有效字符在 中的位置（首位从 0 开始计算），无有效字符返回 -1。

样例输入

输入

ace
abcde

输出

4

输入

fgh
abcde

输出

-1

数据范围

• 的长度
• 的长度

题解

题目要求判断字符串 是否是字符串 的有效子序列，并返回 中最后一个有效字符在 中的位置。可以通过遍历 来匹配 中的字符，记录最后一个匹配字符的位置。

参考代码

• Python

def find_last_position(S, L):
    s_len = len(S)
    l_len = len(L)
    s_index = 0
    last_pos = -1

    for i in range(l_len):
        if s_index < s_len and S[s_index] == L[i]:
            last_pos = i
            s_index += 1
        if s_index == s_len:
            break

    return last_pos if s_index == s_len else -1

if __name__ == "__main__":
    S = input().strip()
    L = input().strip()
    print(find_last_position(S, L))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String S = in.nextLine();
        String L = in.nextLine();
        System.out.println(findLastPosition(S, L));
    }

    public static int findLastPosition(String S, String L) {
        int sLen = S.length();
        int lLen = L.length();
        int sIndex = 0;
        int lastPos = -1;

        for (int i = 0; i < lLen; i++) {
            if (sIndex < sLen && S.charAt(sIndex) == L.charAt(i)) {
                lastPos = i;
                sIndex++;
            }
            if (sIndex == sLen) {
                break;
            }
        }

        return sIndex == sLen ? lastPos : -1;
    }
}

• Cpp

#include <iostream>
#include <string>
using namespace std;

int findLastPosition(const string& S, const string& L) {
    int sLen = S.length();
    int lLen = L.length();
    int sIndex = 0;
    int lastPos = -1;

    for (int i = 0; i < lLen; i++) {
        if (sIndex < sLen && S[sIndex] == L[i]) {
            lastPos = i;
            sIndex++;
        }
        if (sIndex == sLen) {
            break;
        }
    }

    return sIndex == sLen ? lastPos : -1;
}

int main() {
    string S, L;
    getline(cin, S);
    getline(cin, L);
    cout << findLastPosition(S, L) << endl;
    return 0;
}