今日标题链接:正则表达式匹配

正则表达式匹配

难度：较难

描绘

请完成一个函数用来匹配包括’.’和’*’的正则表达式。

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

举例

解题思路

本题不难理解，可是匹配过程中需求考虑的状况比较多，需求谨慎地考虑到每一种状况。

首先，咱们剖析如何匹配一个字符，当用一个字符去和形式串中的字符匹配时，假如形式中的字符是.，那么任何字符都能够匹配:或者，假如两个字符相同，那么能够匹配，接着再去匹配下一个字符。

相对来说，当形式串的第二个字符不是 * 时，问题比较简单:若字符串的榜首个字符和形式串的榜首个字符匹配时，字符害和形式串指针都向后移动一个字符，然后匹配剩余的字符串和形式。假如榜首个字符不匹配，那么就能够直接回来false。

当形式串的第二个字符是 * 时，状况就比较复杂，由于可能有多种不同的匹配方式:

• 不管榜首个字符是否持平，形式串向后移动两个字符，相当于 * 和它前面的字符被忽略，由于 * 能够代表前面的字符呈现0次。
• 假如形式串榜首个字符和字符串榜首个字符匹配，则字符串向后移动一个字符，比较下一位，而形式串此时有两种状况:形式串向后移动两个字符，也能够坚持形式不变 (由于 * 能够代表前面的字符呈现多次)。

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

完成代码（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″。目前给出的数据，只是会存在一个最长的公共子序列

举例

解题思路

动态规划+递归获取；标题要求获取最长公共子序列，咱们肯定要先知道最长到底是多长，因此肯定要先求最长公共子序列的长度，然后根据这个长度获取这个子序列。（注意：子序列不是子串，子串要求一切字符必须接连，子序列不要求接连，只需求相对方位不变）

• 首先对于动态规划，需求清晰状况: 当时处理到的 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<ji<j 且 arri≥arrjarri​≥arrj​。

举例

解题思路

动态规划；

• 状况界说：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();
    }
}