educative.io

Educative

Code with O(n) time complexity

Why this can’t be done in O(n):

class RegxMatch {
static boolean regxMatch(String text, String pattern) {

	int i = pattern.length() - 1;
	int j = text.length() - 1;

	if (text.isEmpty() && pattern.isEmpty())
		return true;
	if (pattern.isEmpty())
		return true;

	while (i > -1 && j > -1) {

		char curPatCh = pattern.charAt(i);

		// if *
		if (curPatCh == '*') {
			i--;
			curPatCh = pattern.charAt(i);
			while(i>0 && curPatCh == pattern.charAt(i-1) ) {
				curPatCh = pattern.charAt(--i);
			}

			// if .
			if (curPatCh == '.') {
				char prev = text.charAt(j - 1);
				while (j >= 0 && j>=i && text.charAt(j) == prev) {
					j--;
					
				}
			} else {
				// other character
				while (j >= 0 && j >=i && text.charAt(j) == curPatCh) {
					j--;
					
				}
			}
			i--;
		}

		// if .
		else if (curPatCh == '.') {
			i--;
			j--;
		}

		// any other character
		else {
			if (text.charAt(j) != curPatCh)
				return false;
			
			i--;
			j--;
		}
	}

	if (i != -1 || j != -1)
		return false;
	
	return true;

}

}