2021/1/21 藏宝图

题目描述

牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。

输入描述

每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10 的不包含空格的可见 ASCII 字符串。

输出描述

输出一行 “Yes” 或者 “No” 表示结果。

示例

输入

x.nowcoder.com
ooo

输出

Yes

解题思路

• 方案一：使用正则表达式查找子序列是否在字符串中（最直接易懂）。
• 方案二：使用动态规划（未优化）。
  1. 动态规划需要明确阶段、状态、边界。
  2. 输入值为两个字符串，即两个字符数组，我们需要建立一个二维数组 arr[m][n]，其中 m 为阶段数， arr[m][n] 为当前状态。
  3. 根据题目描述，将 (ii) 中抽象的概念赋予实际意义。设第 i 阶段的任务为在字符串 s 中寻找字符串 t 里第 i 个位置的字符，如上述实例中字符串 t 为 “ooo” 共三个字符，所以有三个阶段。
  4. 设当前状态 arr[m][n] 表示字符串 s 是否找到了字符串 t 中的当前阶段的字符，若找到，则当前状态 arr[m][n] = max(arr[m-1][n], arr[m][n-1]) + 1; 否则 arr[m][n] = max(arr[m-1][n], arr[m][n-1])。
  5. 最后返回数组最后一个元素 arr[m-1][n-1]，是否等于字符串 t 的长度，如果相等，说明全部匹配，t 为 s 的子序列。
     
• 方案三：使用动态规划（优化方案）
  1. 子序列 t 相对原字符串 s 是有序的，也就是说我们可以记录每一阶段任务中找到匹配字符的坐标，下一次任务的起点就无需再从 0 开始，而是这个坐标的列索引 +1 开始。而且下一次任务如果也找到了匹配值，直接访问这个坐标的数值并 +1 操作即可。
  2. 为了保证第 1 阶段的代码与其他阶段一致，我们添加第 0 阶段使得数组长度变为 arr[m+1][n+1]，其中 arr[0][?] 表示子序列 t 长度为 0 时匹配的个数，arr[?][0] 表示原字符串 s 长度为 0 时匹配的个数，当然这两种情况结果肯定为 0。
     

Java代码实现

import java.util.Scanner;
import java.util.regex.Pattern;

public class Main {
    // 方案一：正则表达式法
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String t = in.nextLine();
        char[] arr = t.toCharArray();
        StringBuilder pattern = new StringBuilder();
        for (char item : arr) {
            pattern.append(".*").append(item);
        }
        pattern.append(".*");
        if (Pattern.matches(pattern.toString(), s)) {
            System.out.print("Yes");
        } else {
            System.out.print("No");
        }
    }

    // 方案三：动态规划
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String t = in.nextLine();
        int rowLen = t.length() + 1;
        int colLen = s.length() + 1;
        int[][] status = new int[rowLen][colLen];
        int prevIndex = 0;
        for (int i = 1; i < rowLen; ++i) {
            for (int j = prevIndex + 1; j < colLen; ++j) {
                if (t.charAt(i-1) == s.charAt(j-1)) {
                    status[i][j] = status[i-1][prevIndex] + 1;
                    prevIndex = j;
                    break;
                }
            }
        }
        if (status[rowLen-1][prevIndex] == t.length()) {
            System.out.print("Yes");
        } else {
            System.out.print("No");
        }
    }
}