(C卷,100分)- 判断字符串子序列（Java & JS & Python）

题目描述

给定字符串 target和 source，判断 target是否为 source 的子序列。

你可以认为target和 source 中仅包含英文小写字母。

字符串 source 可能会很长（长度~=500,000），而 target是个短字符串（长度<=100)。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。

（例如，”abc”是”aebycd”的一个子序列，而”ayb”不是）。

请找出最后一个子序列的起始位置。

输入描述

第一行为target，短字符串（长度 <=100）
第二行为source，长字符串（长度 ~= 500,000）

输出描述

最后一个子序列的起始位置，即最后一个子序列首字母的下标

备注

若在source中找不到target，则输出-1。

用例

题目解析

此题是

的进阶题。

此题不再好用正则来投机取巧了，因为source串中可能存在多个target子串，此时使用/a.*b.*c.*/正则就无法正确匹配了，因为此正则会直接匹配出abcaybec整个字符串，而不是某个子串。而想要构造一个只匹配子串，而不匹配整串的正则非常难，不适合机试。

因此，本题我们还可以使用指针来做。

创建一个指针cursor，来指向target的尾部target.length-1位置，而不是指向target的0位置

因为题目要求最后一个子序列首字母的下标，因此我们反向遍历target串，以及source串，这样的话，匹配到的第一个序列就是符合要求的。

 反向遍历source字符串的每一个字符，与当前cursor指针指向的taget串的字符比较，若相同，则cursor–，若不同，则cursor不变。

当cursor指向0位置时，此时若有source[i]的字符与target[cursor]相同，则i就是题解。

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    System.out.println(getResult(sc.nextLine(), sc.nextLine()));
  }

  public static int getResult(String target, String source) {
    int cursor = target.length() - 1;
    for (int i = source.length() - 1; i >= 0; i--) {
      if (source.charAt(i) == target.charAt(cursor)) {
        cursor--;
        if (cursor < 0) return i;
      }
    }

    return -1;
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    let target = lines[0];
    let source = lines[1];
    console.log(getValidSubStrIndex(target, source));

    lines.length = 0;
  }
});

function getValidSubStrIndex(target, source) {
  let cursor = target.length - 1;
  for (let i = source.length - 1; i >= 0; i--) {
    if (source[i] === target[cursor]) {
      cursor--;
      if (cursor < 0) {
        return i;
      }
    }
  }
  return -1;
}

Python算法源码

# 输入获取
target = input()
source = input()


# 算法入口
def getResult():
    cursor = len(target) - 1
    for i in range(len(source)-1, -1, -1):
        if source[i] == target[cursor]:
            cursor -= 1
            if cursor < 0:
                return i

    return -1


# 调用算法
print(getResult())