最新华为OD机试真题-字符串序列判定(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓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;
}
#华为OD##华为##笔试##秋招##春招#最新华为OD机试-C&D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-C/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 提供OJ在线评测