字符串-正则表达式匹配(思路和实现)

KLQ 2020-04-14 16:17:13 java常见问答 9166

下面给大家分享的是一个正则表达式匹配实例,包括了具体的思路和代码实现,一起来了解一下吧。

题目:

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

注:

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

'*'表示它前面的字符可以出现任意次(包含0次);

匹配是指字符串的所有字符匹配整个模式;

例:

字符串"aaa"和模式"a.a"和"ab*ac*a"匹配,但是和"aa.a"与"ab*a"都不匹配。

思路1:

第一步要考虑到特殊的情况:

1、两个字符串都为空,返回true

2、在第一个字符串不空,而第二个字符串空了,返回false(因为这样,就无法匹配成功了,而假如第一个字符串空了,第二个字符串非空,还是可能匹配成功的。

例:第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次,所以就有可能匹配成功。

随后,就开始匹配第一个字符。

这里可以有两种可能:匹配成功或者是匹配失败。

但是考虑到pattern下一个字符可能是‘*’, 这里我们分两种情况讨论:pattern下一个字符为‘*’或者是不为‘*’:

1、pattern下一个字符不为‘*’:这种情况比较简单,直接匹配当前字符。

假如匹配成功,继续匹配下一个;假如匹配失败,直接返回false。

注意这里的“匹配成功”,除了两个字符相同的情况外,还有一种情况,就是pattern的当前字符为‘.’,同时str的当前字符不为‘’。

2、pattern下一个字符为‘*’的时候,稍微复杂一些,因为‘*’可以代表0个或多个。

这里把这些情况都考虑到:

(1)当‘*’匹配0个字符的时候,str当前字符不变,pattern当前字符后移两位,跳过这个‘*’符号;

(2)当‘*’匹配1个或多个的时候,str当前字符移向下一个,pattern当前字符不变。(这里匹配1个或多个可以看成一种情况,因为:当匹配一个的时候,由于str移到了下一个字符,而pattern字符不变,就回到了上边的情况a;当匹配多于一个字符的时候,也就类于从str的下一个字符继续开始匹配)

这样整理一下,之后再去写代码就要简单的多了。

代码实现:

class Solution
{
    public:
        bool match(char * str, char * pattern)
        {
            if ( * str == '' && * pattern == '')
                return true;
            if ( * str != '' && * pattern == '')
                return false;
            //if the next character in pattern is not '*'
            if ( * (pattern + 1) != '*')
            {
                if ( * str == * pattern || ( * str != '' && * pattern == '.'))
                    return match(str + 1, pattern + 1);
                else
                    return false;
            }
            //if the next character is '*'
            else
            {
                if ( * str == * pattern || ( * str != '' && * pattern == '.'))
                    return match(str, pattern + 2) || match(str + 1, pattern);
                else
                    return match(str, pattern + 2);
            }
        }
};

思路2:

在模式中的第二个字符不是“*”的时候:

一、假如字符串第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的。

二、假如字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。

在模式中的第二个字符是“*”的时候:

假如字符串第一个字符跟模式第一个字符不匹配,那么模式后移2个字符,继续匹配。

假如字符串第一个字符跟模式第一个字符匹配,可以有三种匹配的方式:

(一)模式后移2字符,相当于x*被忽略;

(二)字符串后移1字符,模式后移2字符;

(三)字符串后移1字符,模式不改变,即继续匹配字符下一位,因为*可以匹配多位;

注意:Java里面,要随时检验数组是否越界。

代码实现:

public class Solution
{
    public boolean match(char[] str, char[] pattern)
    {
        if (str == null || pattern == null)
        {
            return false;
        }
        int strIndex = 0;
        int patternIndex = 0;
        return matchCore(str, strIndex, pattern, patternIndex);
    }
    public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex)
    {
        //有效性检验:str到尾,pattern到尾,匹配成功
        if (strIndex == str.length && patternIndex == pattern.length)
        {
            return true;
        }
        //pattern先到尾,匹配失败
        if (strIndex != str.length && patternIndex == pattern.length)
        {
            return false;
        }
        //模式第2个是*,且字符串第1个跟模式第1个匹配,分3种匹配模式;如不匹配,模式后移2位
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*')
        {
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length))
            {
                return matchCore(str, strIndex, pattern, patternIndex + 2) //模式后移2,视为x*匹配0个字符
                    ||
                    matchCore(str, strIndex + 1, pattern, patternIndex + 2) //视为模式匹配1个字符
                    ||
                    matchCore(str, strIndex + 1, pattern, patternIndex); //*匹配1个,再匹配str中的下一个
            }
            else
            {
                return matchCore(str, strIndex, pattern, patternIndex + 2);
            }
        }
        //模式第2个不是*,且字符串第1个跟模式第1个匹配,则都后移1位,否则直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length))
        {
            return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
    }
}

思路3

代码实现:

/*
思路:只有当模式串和字符串同时等于,才可以认为两个串匹配。
在匹配中,对于每个位的匹配可以分为三种情况
1、(相应位匹配||模式串为.&&字符串不是)&&模式串下一位是*
2、(相应位匹配||模式串为.&&字符串不是)&&模式串下一位不是*
3、相应位不匹配&&(模式位不为.||字符串是)
对应1,最复杂。分为*取0,*取1,*>=2三种情况。
*取0对应跳过当前匹配位,继续寻找patter的下一个匹配位,str不变,pattern+2
*取1对应当前匹配位算一次成功匹配,str+1,pattern+2
*取>=2对应一次成功匹配,继续匹配字符串的下一位是否匹配,str+1,pattern不变
三者取或。即只要有一种情况能匹配成功认为字符串就是匹配成功的。
对应2,相当于一次成功匹配,str+1,pattern+1
对应3,匹配失败,直接返回false
*/
class Solution
{
    public:
        bool match(char * str, char * pattern)
        {
            if (str == NULL || pattern == NULL)
                return false;
            return matchCore(str, pattern);
        }
    bool matchCore(char * str, char * pattern)
    {
        if ( * str == '' && * pattern == '')
            return true;
        if ( * str != '' && * pattern == '')
            return false;
        if ( * (pattern + 1) == '*')
        {
            if ( * pattern == * str || ( * pattern == '.' && * str != ''))
                /*
                               matchCore(str,pattern+2):模式串未匹配
                               matchCore(str+1,pattern):模式串已经匹配成功,尝试匹配下一个字符串
                               matchCore(str+1,pat+2):模式串已经成功匹配,并且不匹配下一个字符串内容  注意这里 matchCore(str+1,pat+2)重复考虑了(代码中已经去除),谢谢@chlq的指出 */
                return matchCore(str + 1, pattern) || matchCore(str, pattern + 2);
            else
                return matchCore(str, pattern + 2);
        }
        if ( * str == * pattern || ( * pattern == '.' && * str != ''))
            return matchCore(str + 1, pattern + 1);
        return false;
    }
};

以上的正则表达式匹配思路和代码实现大家都了解了吗?更多的Java实例,可以继续的关注本站的Java实例专栏了解哦。