Xiao Shan

Question

字符串1：只含有英文字母
字符串2：含有英文字母和*，其中符号*表示匹配任意字符0或者多次。

现在给定这样的两个串，要求判断是否匹配？

例如：str1 = “hello”，str2 = “he*o”，则二者匹配；str1 = “hello”，str2 = “he*l”，则不匹配。

Analysis

1.最容易想到的是回溯。

设输入的两个字符串分别为 s和t，其中t可能包含*。我们逐个字符比较

1. 如果t的当前字符不是*，就像普通的串匹配一样，移动s和t
2. 如果t的当前字符是*，假设t后面第一个不是*的字符是x，若没有x，后面都是*，直接匹配成功；
   否则在s中找到从当前位置起后面所有字符x的位置，这时候问题转化成了t中从x开始的子串和s中找到的所有以x为开始的串的匹配问题，递归调用即可，其中任意一个匹配成功，则原串匹配成功,，若都没有匹配成功则匹配失败。

Java源码：

public static boolean isMatch(char[] s, int startS, char[] t, int startT) {
		int i = startS, j = startT;
		while(i<s.length && j<t.length){
	        if (t[j] != '*') {
	        	if(s[i] == t[j]){
	        		i++;
	        		j++;
	        	} else {
	        		return false;
	        	}
	        } else {
	            do {
	            	j++;
	            } while (j<t.length && t[j] == '*');

	            if (j==t.length) {
	            	return true;
	            }

	            for ( ; i<s.length; i++) {
	            	if (s[i] == t[j] && isMatch(s, i+1, t, j+1)) {
	                    return true;
	            	}
	            }

	            return false;
	        }
	    }

		if(i< s.length) {
			return false;
		} else {
			while (j < t.length && t[j] == '*') {
				j++;
			}
			if(j<t.length) {
				return false;
			} else {
				return true;
			}
		}
	}

这种递归搜索，存在很多重复的状态，如果遇到”aaaaaaaaaaaaaa”，”a*a*a*a*a*a*a*a*a*a*a”这样的输入，会达到2ⁿ的复杂度。一种优化就是通过备忘录记忆已有的状态，可以时间空间复杂度都优化到n²，这里代码不写了。

2. 如果不想用递归，可以考虑另外一种思路是

对于t，可以看成被一些*串（连续的*组成的子串）划分成了一组跟s一样纯由字母组成的子串。
这样问题就转化成了在s中寻找一个子串序列。

1. 开始时还像普通的串匹配一样，移动s和t，直到t遇到第一个*
2. 然后t后面的部分假设被*串划分成如下一组字符字串：t1, t2, t3
3. 那么问题变成了从s的当前位置开始找t1，如果没找到，则不匹配；如果找到（这时候有可能s中存在很多t1，我们只需考虑第一个。因为如果第一个能导致整个串匹配成功，则已经达到我们的目的，其他的不用考虑，因为我们并不需要输出所有的匹配。而如果第一个都不能使整个串匹配成功，后面情况由于可供匹配的子串更短，更不可能成功。），则继续从s匹配了t1的部分后面继续找t2；如此操作直至所有的子串都找到时，则整个匹配成功，否则任何一处没匹配则整个匹配失败

为了方便操作，开始时把s和t尾部相等的字符都截掉了。
Java源码：

public static boolean isMatch(char[] s, char[] t) {
		//cut off the tail of non-* characters
		int i=s.length-1,j=t.length-1;
		while(i>-1 && j>-1 && s[i] == t[j]) {
			i--;
			j--;
		}

		int endS = i+1, endT = j+1;
		i=j=0;
		while(i<endS && j<endT && s[i] == t[j]) {
			i++;
			j++;
		}
		if(j==endT) {//t has no *
			if(i==endS) {//t equals to s
				return true;
			} else {
				return false;//s is longer than t, unequal
			}
		}
		if(t[j] != '*') {// not match for a non-* character
			return false;
		}
		// the first * is found

		int subStringStart = j;
		int subStringEnd = j;
		while (j < endT) {
			while (j < endT
					&& t[j] == '*') {
				j++;
			}
			if(j==endT) {
				return true;
			}
			// get the first non-* char
			subStringStart = j;

			while (j < endT
					&& t[j] != '*') {
				j++;
			}
			// get the last non-* char
			subStringEnd = j-1;

			//match it in s using normal string match algorithm
			i = isNormalMatch(s, i, endS-1, t, subStringStart, subStringEnd);
			if(i == -1) {
				return false;
			} else if(i==endS) {
				return true;
			}
		}

		// t ends as a non-* character but s not ends yet
		return false;
	}

	//KMP
	private static int isNormalMatch(char[] text, int textStart, int textEnd, char[] pattern, int patternStart, int patternEnd) {
                if(textStart>textEnd || patternStart > patternEnd) {
                    return -1;
                }
		char[] s1 = Arrays.copyOfRange(text, textStart, textEnd+1);
		char[] s2 = Arrays.copyOfRange(pattern, patternStart, patternEnd+1);
		int[] next = new int[patternEnd-patternStart+1];
		caculateNext(s2,next);
		int i = isMatch(s2,s1,next);
		if(i != -1) {
			i = i + textStart + 1;
		}
		return i;
	}

	private static int isMatch(char[] patternStamp, char[] textStamp, int[] next) {
		int i = 0, j = 0;
		while (j < patternStamp.length && i < textStamp.length) {
			if (j == -1 || patternStamp[j] == textStamp[i]) {
				i++;
				j++;
			} else {
				j = next[j];
			}
		}

		if (j == patternStamp.length) {
			return i-j;
		} else {
			return -1;
		}
	}

	private static void caculateNext(char[] pattern, int[] next) {
		next[0] = -1;

		int i = 0, j = -1;
		while(i<pattern.length-1) {
			if(j==-1 || pattern[i] == pattern[j]) {
				i++;
				j++;
				next[i] = j;
			} else {
				j = next[j];
			}
		}
	}

这种方法没有递归，而且s的指针只从头到尾遍历了一次，t的指针在大循环中也是从头到尾遍历一次，只是在KMP时在子串匹配中还有移动，不过总的来说仍然是线性的，所以整个算法匹配，复杂度跟串长成线性关系，比之前的递归搜索效率高了很多。

related post

• [uc]LocalMark - 页面书签
• [userChrome script]flybar - 居中地址栏和搜索框 (扩展版 - flybar)
• pentadactyl试用记
• [userChrome script]firelaunchy - 从firefox快速启动应用程序
• [KeySnail]编辑模式下使用可输入字符作为快捷键

Filed under:
algorithm by admin