字符串匹配

【编程题目 |200分】字符串匹配【2021, 2022 H1 考试题】

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，

编码后请点击”保存并调试“按钮进行代码提交。

■ 题目描述

【字符串匹配】

给你一个字符串数组（每个字符串均由小写字母组成）和一个字符规律（由小写字母和.和*组成），识别数组中哪些字符串可以匹配到字符规律上。

‘.’ 匹配任意单个字符，’*’ 匹配零个或多个前面的那一个元素，所谓匹配，是要涵盖整个字符串的，而不是部分字符串。

输入描述

第一行为空格分割的多个字符串，1<单个字符串长度<100，0，1<字符串个数<100

第二行为字符规律，1<字符串个数<100

第二行为字符规律，1<=字符规律长度<=50

不需要考虑异常场景。

输出描述

匹配的字符串在数组中的下标（从0开始），多个匹配时下标升序并用,分割，若均不匹配输出-1

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

ab aab

.*

输出

0,1

示例2 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

ab abc bsd

.*

输出

0,1,2

示例3 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

avd adb sss as

adb

输出

1

C++ DP解法

#include<bits/stdc++.h>

using namespace std;

void SplitString(string input, vector<string> &output, char patten)
{
    string one_word;
    int j = 0;
    input += patten;
    for (int i = 0; i < input.size(); i++) {
        if (input[i] == patten) {
            one_word = input.substr(j, i - j);
            output.push_back(one_word);
            one_word.clear();
            j = i + 1;
        }
    }
}

剩余50%内容，订阅会员后查看

C++ 递归解法

#include<bits/stdc++.h>

using namespace std;

void SplitString(string input, vector<string> &output, char patten)
{
    string one_word;
    int j = 0;
    input += patten;
    for (int i = 0; i < input.size(); i++) {
        if (input[i] == patten) {
            one_word = input.substr(j, i - j);
            output.push_back(one_word);
            one_word.clear();
            j = i + 1;
        }
    }
}

剩余50%内容，订阅会员后查看

JAVA

import java.util.Scanner;

public class StringMatch {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] StringArray = input.split(" ");
        String line = scanner.nextLine();
        StringBuilder sb = new StringBuilder();

剩余50%内容，订阅会员后查看

Python

剩余50%内容，订阅会员后查看

STICK永久会员

打赏 收藏 海报 链接