当前位置：网站首页>字符串匹配问题小结
字符串匹配问题小结
2022-08-08 06:26:00 【bug_Cat】
字符串匹配问题小结
刷Leetcode时，发现有两个字符串匹配问题很巧妙，所以记录一下
正则表达式匹配
问题描述
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码
回溯思想：
class Solution {
char[] str;
char[] pattern;
public boolean isMatch(String s, String p) {
if (s==null||p==null) {
return false;
}
this.str = s.toCharArray();
this.pattern = p.toCharArray();
return matchCore(0,0);
}
/*** * * @param sStart str 开始的位置 * @param pStart pattern 开始的位置 * @return */
boolean matchCore(int sStart,int pStart){
if (sStart==str.length && pStart==pattern.length) return true;
if (sStart!=str.length && pStart==pattern.length) return false;
//说明第二个为 *
if (pStart<pattern.length-1 && pattern[pStart+1]=='*') {
if (sStart!=str.length && (pattern[pStart]==str[sStart]||pattern[pStart]=='.')) {
//相等时，需要进行判断
//分别为 *当作一个，当作多个，当作没有
return matchCore(sStart+1, pStart+2)||matchCore(sStart+1, pStart) || matchCore(sStart, pStart+2);
}else{
//不相等时，当这个*不存在
return matchCore(sStart, pStart+2);
}
}
if (sStart!=str.length && (pattern[pStart]==str[sStart]||(pattern[pStart]=='.' )))
return matchCore(sStart+1, pStart+1);
return false;
}
}
回溯比较好理解，代码也比较好实现，总结来说就：
当pattern[pStart]==str[sStart]||(pattern[pStart] ==’.’）时
pattern和str都访问下一个就行
pattern[pStart+1]==’’（第二个字符是‘ *’）时，分情况讨论：
- pattern[pStart]== str[sStart]||pattern[pStart] ==’.’),那么进行递归判断，
- sStart+1, pStart+2，‘*‘当一个字符
- sStart+1, pStart，‘*‘当多个字符
- sStart, pStart+2，’*‘当多个字符
- pattern[pStart]== str[sStart]||pattern[pStart] ==’.’),那么进行递归判断，
动态规划：
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
//代表s的i和p的j的匹配
boolean[][] f = new boolean[m + 1][n + 1];
//表示没有字符时
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
}
else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
public boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
动态规划主要是要想出子问题以及动态转移方程。先给个表格，显示一下子问题的结构
| c | * | a | * | b | |
|---|---|---|---|---|---|
| a | F | F | T | ||
| a | T | T | |||
| b | T |
转移大概这样：
状态转移方程：
- 当p[j]为字母和s[i]匹配时或者p[j]为’.‘，f[i][j] = f[i - 1][j - 1] (比较好理解)
- 当p[j]为’*‘时， f[i][j] = f[i][j - 2]||f[i - 1][j]
具体可以参考：
- https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/
- https://leetcode-cn.com/problems/regular-expression-matching/solution/dong-tai-gui-hua-zen-yao-cong-0kai-shi-si-kao-da-b/
通配符匹配
问题描述
给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wildcard-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码
回溯思想
class Solution {
char[] str;
char[] pattern;
public boolean isMatch(String s, String p) {
if (s==null||p==null) {
return false;
}
this.str = s.toCharArray();
this.pattern = p.toCharArray();
return matchCore(0,0);
}
/*** * * @param sStart str开始的地方 * @param pStart pattern 开始的位置 * @return */
boolean matchCore(int sStart,int pStart){
if (sStart==str.length && pStart==pattern.length) return true;
if (sStart!=str.length && pStart==pattern.length) return false;
// if(sStart>=str.length && pattern[pStart]!='*') return false;
if(sStart<str.length && pattern[pStart]=='*'){
//分别为 * 代表空、1个字符、多个字符
return matchCore(sStart, pStart+1) || matchCore(sStart+1, pStart+1) || matchCore(sStart+1, pStart);
}else if (sStart<str.length && pattern[pStart]==str[sStart]||(pattern[pStart]=='?')) {
return matchCore(sStart+1, pStart+1);
}else if (sStart==str.length && pattern[pStart]=='*') {
return matchCore(sStart, pStart+1);
}
return false;
}
}
思路和上一题类似
动态规划:
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
//dp[i][j表示 s 第i个 到p第j个是否匹配
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <=n; i++) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = true;
}
else {
break;
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}
可以参照这个思路:https://leetcode-cn.com/problems/wildcard-matching/solution/yi-ge-qi-pan-kan-dong-dong-tai-gui-hua-dpsi-lu-by-/
总结
目前就记录这两题，后续再加
边栏推荐
- BiLSTM实现imdb情感分类任务
- C语言-文件中标准IO的常用函数总结
- jupyter notebook添加目录
- Vivado安装—Xilinx design tool already exists for 2019.1,specify a different program program group entr
- 如何使用conda，pip安装、更新、查看和卸载重装Pytorch？
- Unity_预制体批量编辑器
- Unity3D物体上下左右旋转(不受物体自身坐标轴影响)
- Chained queue push and pop related operations
- NVIDIA CUDA 高度并行处理器编程（九）：并行模式：稀疏矩阵-向量乘法
- Bugku faster
猜你喜欢
C language judges the problem of big and small endian storage
Industry Research: Analysis of the Status and Prospects of the Pension Insurance Market in 2022
【图形学】13 UnityShader语义（一）
UGUI_编辑器扩展与常用优化
rhcsa——第三天
神经网络对数据的要求,神经网络分析相关性
Folder permission configuration for Unity local IIS service construction
C语言实现链表的增删查改以及OJ题讲解
Paramenter-Efficient Transfer Learning for NLP
![[总结] Unity Lightmap使用总结](/img/a8/ff6dc01e7a077ad2b365be40c2ed09.png)
[总结] Unity Lightmap使用总结
随机推荐
C language judges the problem of big and small endian storage
PyTorch向量变换基本操作
Variational Inference with Normalizing Flows
深度神经网络的训练过程,深度神经网络训练方法
Unity object color gradient effect (judgment logic implementation)
文件常用操作 IO流原理及分类
神经网络预测值几乎一样,神经网络为什么能预测
P03 线程安全 synchronized Lock
ResNet网络结构详解、完整代码实现
Unity_雷达图（属性图）+ UI动画
何恺明2017CVPR大会上演讲PPT,非常适合ResNet学习者！
HDU 6029 个人分析
神经网络和多元线性回归,神经网络多元线性回归
神经网络原理的简单介绍,神经网络原理及应用
栈队列OJ题分享及讲解
神经网络二分类问题范例,神经网络解决分类问题
ESP32 温湿度和气体传感器驱动
Unity学习笔记 03 —— 三维数学
CSDN21天学习挑战赛之选择排序
中序表达式转为后序表达式