字符串序列判定 - 华为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 i = 0, ans = -1;
        for (int j = 0; j < n2; j++) {
            if (s.charAt(i) == t.charAt(j)) {
                if (++i == n1) {
                    ans = j;
                    break;
                }
            }
        }

        System.out.println(ans);
    }
}
// AC 60%

输出描述

S串最后一个有效字符在L中的位置。

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 i = 0, ans = -1;
        for (int j = 0; i < n1 && j < n2; j++) {
            if (s.charAt(i) == t.charAt(j)) {
                ans = j;
                i++;
            }
        }

        System.out.println(ans);
    }
}
// AC

Python

S, L = input(), input()
n1, n2 = len(S), len(L)

i, j, ans = 0, 0,-1
while i < n1 and j < n2:
    if S[i] == L[j]:
        i += 1
        ans = j
    j += 1

print(ans)

C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s,t;
    cin >> s >> t;
    int n1= s.size(), n2 = t.size();
    int i = 0, ans = -1;
    for(int j = 0; i < n1 && j < n2; j++) {
        if(s[i] == t[j]) {
            ans = j;
            i++;
        }
    }

    cout << ans << endl;

    return 0;
}

解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。