剣指offer 19-正規表現マッチングC++

タイトルの説明は1つの関数を実現して‘を含む’をマッチングしてください.と'の正規表現.モードの文字'.'任意の文字を表し、''はその前の文字が任意の回数(0回を含む)現れることを表す.本題では、マッチングとは、文字列のすべての文字がモード全体に一致することを意味します.例えば、文字列「aaa」は、パターン「a.a」および「abaca」と一致するが、「aa.a」および「ab*a」と一致しない.
構想1:再帰、剣指offer書の解法を参考にする.

class Solution {
public:
	bool match(char* str, char* pattern)
	{
		if (str == nullptr || pattern == nullptr) return false;
		return matchSub(str, pattern);
	}
	bool matchSub(char* str, char* pattern) {
		if (*str == '\0'&&*pattern == '\0') return true;
		if (*str != '\0'&&*pattern == '\0') return false;   // *str == '\0'&&*pattern != '\0'    ："",".*"  true
		if (*(pattern + 1) == '*') {
			if (*pattern == *str || (*pattern == '.'&& *str != '\0')) 
				return matchSub(str + 1, pattern + 2)
					|| matchSub(str + 1, pattern)
					|| matchSub(str, pattern + 2);
			else
				return matchSub(str, pattern + 2);
		}
		if (*pattern == *str || (*pattern == '.'&& *str!='\0')) 
			return matchSub(str + 1, pattern + 1);

		return false;
	}
};

考え方2:重複するサブ問題を含み,動的計画を考える

class Solution {
public:
	bool match(string str, string pattern)
	{
		if (pattern.empty()) return str.empty();
		str = " " + str;   //         ，  aa a*   ab c*ab     ，          
		pattern = " " + pattern;
		vector<vector<bool>> dp(str.size() + 1, vector<bool>(pattern.size() + 1, false));
		dp[0][0] = true;
		for (int i = 1; i < str.size()+1; i++) {  
			for (int j = 1; j < pattern.size()+1; j++) {
				if (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1])  
					dp[i][j] = dp[i - 1][j - 1]; 
				else if (pattern[j - 1] == '*') {
					if (pattern[j - 2] != str[i - 1] && pattern[j - 2] != '.')   
						dp[i][j] = dp[i][j - 2];   //  0   aaa ab*aa
					else
						dp[i][j] = dp[i - 1][j]  //     aaaa aa*a  ->      0 
							|| dp[i][j - 2];   //  0  aaa aa*a
				}
			}
		}
		return dp[str.size()][pattern.size()]; //           
	}
};

まとめ:

p[j]==s[i]:dp[i][j]=dp[i-1][j-1]

p[j]=='.':dp[i][j] = dp[i-1][j-1]

p[j]=='*':1>p[j-1]!=s[i]:dp[i][j]=dp[i][j-2]2>p[j-1]==s[i]‖p[j-1]=='.':

dp[i][j]=dp[i-1][j]マッチング複数回

dp[i][j]=dp[i][j-2]マッチング0回