每日一刷《剑指offer》字符串篇之正则表达式匹配

简介: 每日一刷《剑指offer》字符串篇之正则表达式匹配

每日一刷《剑指offer》字符串篇之正则表达式匹配

正则表达式匹配

难度:较难

描述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。

1.模式中的字符'.'表示任意一个字符

2.模式中的字符'*'表示它前面的字符可以出现任意次(包含0次)。

在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"abaca"匹配,但是与"aa.a"和"ab*a"均不匹配

数据范围

1.str 只包含从 a-z 的小写字母。

2.pattern 只包含从 a-z 的小写字母以及字符 . 和 ,无连续的 ''。

3. 0≤str.length≤26

4. 0≤pattern.length≤26

举例

image.png

解题思路

本题不难理解,但是匹配过程中需要考虑的情况比较多,需要谨慎地考虑到每一种情况。

首先,我们分析如何匹配一个字符,当用一个字符去和模式串中的字符匹配时,如果模式中的字符是.,那么任何字符都可以匹配:或者,如果两个字符相同,那么可以匹配,接着再去匹配下一个字符。

相对来说,当模式串的第二个字符不是 * 时,问题比较简单:若字符串的第一个字符和模式串的第一个字符匹配时,字符害和模式串指针都向后移动一个字符,然后匹配剩余的字符串和模式。如果第一个字符不匹配,那么就可以直接返回false。

当模式串的第二个字符是 * 时,情况就比较复杂,因为可能有多种不同的匹配方式:

  • 无论第一个字符是否相等,模式串向后移动两个字符,相当于 * 和它前面的字符被忽略,因为 * 可以代表前面的字符出现0次。
  • 如果模式串第一个字符和字符串第一个字符匹配,则字符串向后移动一个字符,比较下一位,而模式串此时有两种情况:模式串向后移动两个字符,也可以保持模式不变 (因为 * 可以代表前面的字符出现多次)。

如下图所示,当匹配进入状态2并目字符串的字符是a时,有两种选择: 进入状态3或者保持状态2。

image.png

实现代码(java)


public class Solution {
    public boolean match(char[] str, char[] pattern){
        /*
        思路:比较前两个字符,递归比较
        */
        if(str==null || pattern==null)
            return false;
        return match(str,0,pattern,0);
    }
    public boolean match(char[] str,int i,char[] pattern,int j){
        if(i==str.length && j==pattern.length)//都为空
            return true;
        if(i<str.length && j==pattern.length)//模式串为空
            return false;
        //以下j一定是<len
        if(j+1<pattern.length && pattern[j+1]=='*'){ //第二个字符是*
            if((i<str.length && str[i]==pattern[j]) ||(i<str.length && pattern[j]=='.') ) //第一个字符相等,有三种情况
                return match(str,i,pattern,j+2) || match(str,i+1,pattern,j+2) || match(str,i+1,pattern,j);
                //分别代表匹配0个,1个和多个 
            else //第一个字符不等
                return match(str,i,pattern,j+2);
        }else{     //第二个字符不是*
            if((i<str.length && str[i]==pattern[j]) || ( pattern[j]=='.'&& i< str.length))
                return match(str,i+1,pattern,j+1);
            else
                return false;
        }
    }
}

学习完本题的思路你可以解决如下题目:

BM65 最长公共子序列(二)

最长公共子序列(二)

难度:中等

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子序列。如果最长公共子序列为空,则返回"-1"。目前给出的数据,仅仅会存在一个最长的公共子序列

举例

image.png

解题思路

动态规划+递归获取;题目要求获取最长公共子序列,我们肯定要先知道最长到底是多长,因此肯定要先求最长公共子序列的长度,然后根据这个长度获取这个子序列。(注意:子序列不是子串,子串要求所有字符必须连续,子序列不要求连续,只要求相对位置不变)

  • 首先对于动态规划,需要明确状态: 当前处理到的 s1 和 s2 分别的第 i 和第 j 个字符
  • 定义状态数组:dp[i][j]表示从左到右,当处理到s1的第i个元素和s2的第j个元素时的公共子序列
  • 状态初始化,即当i==0或j==0的情况,dp[i][j]为"",因为空字符串没有公共子序列
  • 状态转移
  • 当前字符相等,则添加结果,i 和 j 指针右移,状态转移方程为:dp[i][j] = dp[i-1][j-1] + s1.charAt(i-1);
  • 当前字符不相等,则还需要分两种情况,取长度较长的情况,状态转移方程为: dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length() ? dp[i-1][j] : dp[i][j-1]

实现代码(java)


import java.util.*;
public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        // 明确状态: 当前需要处理的s1和s2分别前i和前j个元素
        // dp[i][j]表示从左到右,当处理到s1的第i个元素和s2的第j个元素时的公共子序列
        String[][] dp = new String[len1 + 1][len2 + 1];
        // base case:当i==0或j==0的情况,dp[i][j]为"",因为空字符串没有公共子序列
        for(int i = 0; i <= len1; i++) {
            // j == 0
            dp[i][0] = "";
        }
        for(int j = 0; j <= len2; j++) {
            // i == 0
            dp[0][j] = "";
        }
        // 状态转移
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                // 当前字符相等,则添加结果
                if(s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1] + s1.charAt(i-1);
                } else {
                    // 当前字符不相等,则还需要分两种情况,取长度较长的情况
                    dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length() ? dp[i-1][j] : dp[i][j-1];
                }
            }
        }
        return dp[len1][len2] == "" ? "-1" : dp[len1][len2];
    }
}

学习完本题的思路你可以解决如下题目: BM71.最长上升子序列(一)

最长上升子序列(一)

难度:中等

描述

给定一个长度为 n 的数组 arr,求它的最长严格上升子序列的长度。

所谓子序列,指一个数组删掉一些数(也可以不删)之后,形成的新数组。例如 [1,5,3,7,3] 数组,其子序列有:[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是 严格上升 的,当且仅当该序列不存在两个下标 ii 和 jj 满足 i

举例

image.png

解题思路

动态规划;

  • 状态定义:dp[i]dp[i]dp[i]表示以下标i结尾的最长上升子序列的长度。
  • 状态初始化:以任意下标结尾的上升子序列长度不小于1,故初始化为1。
  • 状态转移:遍历数组中所有的数,再遍历当前数之前的所有数,只要前面某个数小于当前数,则要么长度在之前基础上加1,要么保持不变,取两者中的较大者。即dp[i]=Math.max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+1)。

实现代码(java)


import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        int n=arr.length;
        //特殊请款判断
        if(n==0) return 0;
        //dp[i]表示以下标i结尾的最长上升子序列长度
        int[] dp=new int[n];
        for(int i=0;i<n;i++){
            //初始化为1
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    //只要前面某个数小于当前数,则要么长度在之前基础上加1,要么保持不变,取较大者
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        //返回所有可能中的最大值
        return Arrays.stream(dp).max().getAsInt();
    }
}



相关文章
|
1月前
|
JavaScript 前端开发
JavaScript随手笔记 --- 用正则表达式匹配字符串是否为运算公式
JavaScript随手笔记 --- 用正则表达式匹配字符串是否为运算公式
|
5月前
|
Python
133 python高级 - 正则表达式(原始字符串)
133 python高级 - 正则表达式(原始字符串)
28 0
|
6月前
|
C++
使用 ABAP 正则表达式提高字符串解析的执行效率
使用 ABAP 正则表达式提高字符串解析的执行效率
60 0
|
7月前
|
程序员
用正则表达式判断字符串形式正误(例:判断电话号码属地是否为中国大陆)
用正则表达式判断字符串形式正误(例:判断电话号码属地是否为中国大陆)
44 0
|
1月前
|
Linux Perl
使用awk和正则表达式过滤文本或字符串 - 详细指南和示例
使用awk和正则表达式过滤文本或字符串 - 详细指南和示例
60 0
|
4月前
|
算法
【面试算法——动态规划 21】正则表达式匹配(hard)&& 交错字符串
【面试算法——动态规划 21】正则表达式匹配(hard)&& 交错字符串
|
4月前
通过正则表达式获取字符串中的省市区
通过正则表达式获取字符串中的省市区
49 0
通过正则表达式获取字符串中的省市区
|
8月前
|
Python
【从零学习python 】62. Python正则表达式:强大的字符串匹配工具
【从零学习python 】62. Python正则表达式:强大的字符串匹配工具
40 0
|
1月前
|
编译器 Python
Python正则表达式的7个使用典范(推荐)
Python正则表达式的7个使用典范(推荐)
22 0