正則表達式匹配


難度級別
經常問 土磚 亞馬遜 蘋果 彭博社 Coursera 易趣 Facebook 高盛 谷歌 Microsoft微軟
回溯 動態編程

正則表達式匹配 問題,我們給了兩個字符串(假設它 x)僅由小寫字母和第二個字母組成(假設 y)由小寫字母和兩個特殊字符組成,即“。” 和 ”*”。 任務是查找第二個字符串是否與第一個字符串匹配 或不。 如果匹配,則打印 “真正” 否則打印 “錯誤的”.

此處使用的兩個字符表示:

“。” –模式匹配任何單個字符,即“。” 可以用匹配第一個字符串所需的任何字符替換

“ *” –模式匹配出現在“ *”之前的0個或多個字符,即,“ *”可以被前面的任何字符替換為零個或多個,以匹配第一個字符串

備註:

  • x可以為空,也可以僅包含小寫字母。
  • y也可以為空,也可以僅包含小寫字母或僅包含“。”的字符。 或“ *”或兩者(即小寫字母和字符,如“。”和“ *”)

輸入

x =“ aa”

y =“ a”

產量

解釋

由於y與整個字符串不匹配,即,“ a”(y)與字符串“ aa”(x)不匹配。

輸入

x =“ aa”

y =“ a *”

產量

解釋

“ *”表示前一個字母重複零次或更多次並刪除特殊字符。 因此,通過在字符串“ a *”中重複“ a”,它將變為“ aa”,並且兩個字符串將變為相同。

輸入

x =“ acb”

y =“ ab”

產量

解釋

在這裡,我們可以替換為“。” 用任何字符替換“。” 在“ ab”乘“ c”中,我們將獲得所需的字符串,即acb,並且兩個字符串都將變為true。

輸入

x =“ ab”

y =“。*”

產量

解釋

“。*”表示“任何字符(。)的零個或多個(*)”。

算法

有很多解決此問題的方法,但是最有效的方法是使用 動態編程.

  1. 得到兩者的長度 “X”的“ y” 用一些變數說 “m”個“ n” 分別。
  2. 檢查是否 “m”個 等於 “0” 然後返回打印 .
  3. 初始化2d數組(例如dp),其長度為 “X”的 作為行和 “ y” 作為列。
  4. 標記 排列 為假。
  5. 初始化 “0,0” 數組索引為
  6. 運行for循環直到 “m”個 從1
    1. 在內部進行循環檢查,如果y [i-1] =='*'
      1. 如果是,則dp [0] [i] = dp [0] [j-1]
  7. 初始化一個嵌套的for循環:1到XNUMX的循環 “m”個 其次是1到 “ n”
    1. 在for循環檢查中,如果y [j-1] =='*'
      1. 如果是,則dp [i] [j] = dp [i] [j – 1] || dp [i – 1] [j]
    2. 否則檢查y [j – 1] =='。 || x [i – 1] == y [j – 1]
      1. 如果是,則dp [i] [j] = dp [i – 1] [j – 1]
    3. 否則將dp [i] [j]標記為false,即dp [i] [j] == false
  8. 打印dp [n] [m]的結果,即dp的最後一個索引

 C ++中用於正則表達式匹配的實現

#include <bits/stdc++.h>
using namespace std;

bool isMatch(char x[], char y[])
{
    int n = strlen(x);
    int m = strlen(y);

    if (m == 0)
        return (n == 0);

    bool dp[n + 1][m + 1];

    memset(dp, false, sizeof(dp));

    dp[0][0] = true;

    for (int i = 1; i <= m; i++)
    {
        if (y[i - 1] == '*')
        {
            dp[0][i] = dp[0][i - 1];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (y[j - 1] == '*')
            {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }

            else if (y[j - 1] == '.' || x[i - 1] == y[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1];
            }

            else
            {
                dp[i][j] = false;
            }
        }
    }

    return dp[n][m];
}

int main()
{
    char x[] = "acb";
    char y[] = "a.b";

    cout<< boolalpha<<(isMatch(x, y));
    return 0;
}
true

Java中用於正則表達式匹配的實現

import java.util.Arrays;
public class solution {

  static boolean isMatch(String x, String y) {
    int n = x.length();
    int m = y.length();

    if (m == 0)
      return (n == 0);

    boolean[][] dp = new boolean[n + 1][m + 1];

    for (int i = 0; i<n + 1; i++) {
      Arrays.fill(dp[i], false);
    }

    dp[0][0] = true;

    for (int j = 1; j<= m; j++) {
      if (y.charAt(j - 1) == '*') {
        dp[0][j] = dp[0][j - 1];
      }
    }

    for (int i = 1; i<= n; i++) {
      for (int j = 1; j<= m; j++) {

        if (y.charAt(j - 1) == '*') {
          dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
        } else if (y.charAt(j - 1) == '.' || x.charAt(i - 1) == y.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = false;
        }
      }
    }

    return dp[n][m];
  }

  public static void main(String args[]) {
    String x = "acb";
    String y = "a.b";

    System.out.println((isMatch(x, y)));

  }
}
true

正則表達式匹配的複雜度分析

時間複雜度

O(m×n)其中 m 是的長度 “X”的n 是的長度 “ y”

空間複雜度

O(m×n)其中 m 是的長度 “X”的n 是的長度 “ y”

參考