程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Wildcard Matching

leetcode筆記:Wildcard Matching

編輯:關於C++

一. 題目描述

Implement wildcard pattern matching with support for ‘?’ and ‘*’.

‘?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

二. 題目分析

題目的大意是,給出兩串字符串sp,規定符號?能匹配任意單個字符,*能匹配任意字符序列(包括空字符序列)。如果兩串字符串完全匹配則返回true

該題的難點主要在於出現*時的匹配操作。和網上大多數做法相似,一開始使用遞歸完成,結果總是超時。後來使用幾個變量用於記錄遇到p中的*時的下標,每次遇到一個*,就保留住當前字符串sp的下標,然後s從當前下標往後掃描,如果不匹配,則s的下標加一,重復掃描。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int s_size = s.size();
        int p_size = p.size();
        int s_index = 0, p_index = 0;
        int temp_s_index = -1, temp_p_index = -1;
        while (s_index < s_size)
        {
            if (p[p_index] == '?' || p[p_index] == s[s_index])
            {
                ++p_index;
                ++s_index;
                continue;
            }
            if (p[p_index] == '*') 
            {
                temp_p_index = p_index;
                temp_s_index = s_index;
                ++p_index;
                continue;
            }
            if (temp_p_index >= 0)
            {
                // 字符串p可能有多個*,因此只要出現過*,則需要更新當前匹配的下標
                p_index = temp_p_index + 1;
                s_index = temp_s_index + 1;
                // 當前坐標s與p不匹配,則s的坐標在原基礎上加一,繼續循環
                ++temp_s_index; 
                continue;
            }
            return false;
        }
        while (p[p_index] == '*') ++p_index;
        return p_index == p_size;
    }
};

四. 小結

這種題目一般遞歸的思路還是首選,但遞歸的最大缺點就是耗時。該題若使用動態規劃也可以解決,但是未必能達到以上方法的

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved