LeetCode 44--ワイルドカード照合

タイトルの説明:
1つの文字列(s)と1つの文字パターン(p)が与えられ、'?'と'*'をサポートするワイルドカードマッチングが実現される.

'?'           。
'*'          （      ）。

2つの文字列が完全に一致してこそ、一致に成功します.
説明:

sは空であり、a-zからの小文字のみを含むことができる.

pは空である可能性があり、a-zからの小文字のみを含む、?および*。から

の文字を含む. ： p ， s ， p s 。 ， i j，i s i ，j p j ，dp[i][j]=true s i p j ， ， dp[i][j] 。 ， ，‘？’ p ，‘*’ p ，‘*’ p ，‘*’ 0 p 。 dp[i][j]=true s i 、p j ， dp[i][j]=true， ：

dp[i-1][j-1]=true， s.charAt(i-1)==p.charAt(j-1);

dp[i][j-1]=trueであり、p.charAt(j-1)='*'である.

dp[i-1][j]=trueであり、p.charAt(j-1)='*'である場合、'*'はsのi番目の文字に一致することを示す.

便宜上、文字列の最初の文字は1から始まり、コードは以下の通りです.

private static boolean isMatch(String s,String p) {
	int m=s.length();
	int n=p.length();
	boolean[][] dp=new boolean[m+1][n+1];
		
	dp[0][0]=true;
	for(int j=1;j<=n;j++) dp[0][j]=dp[0][j-1]&&p.charAt(j-1)=='*';
	for(int i=1;i<=m;i++) {
		for(int j=1;j<=n;j++) {
			if(p.charAt(j-1)=='?') dp[i][j]=dp[i-1][j-1];
			else {
				dp[i][j]=(dp[i-1][j-1]&&s.charAt(i-1)==p.charAt(j-1))||
						(dp[i-1][j]&&p.charAt(j-1)=='*')||
						(dp[i][j-1]&&p.charAt(j-1)=='*');
			}
		}
	}
		
	return dp[m][n];
		
}

考え方2:
貪欲なアルゴリズムを使う.パターン文字列pのj番目の文字が"*"である場合、j_start=j,i_start=iは、このとき「*」と文字列sのi番目の文字の位置を記録し、その後「*」の次の文字にジャンプし、pのj+1、sのiから文字マッチングを行う(この場合「*」に相当して0文字がマッチングされる).マッチングが完了しない場合は、j_を使用します.start i_startレコードの初期位置は,pのj+1,sのi+1からマッチングする.のマッチングが完了するまでループします.
コードは次のとおりです.

private static boolean isMatch(String s,String p) {
	int m=s.length(),n=p.length(),i_start=-1,j_start=-1,i=0,j=0;
	while(i-1){
			j=j_start;
			i=i_start+1;
		}
		else {
			return false;
		}
	}
		
	while(j

動的計画と比較して,貪欲アルゴリズムの空間的複雑さはO(1)である.