// Check if string follows order of characters defined by a pattern or not | Set 2

StringMatchesPattern2.js

// Check if string follows order of characters defined by a pattern or not | Set 2

// Given an input string and a pattern, check if characters in the input string follows the same order as determined by characters present in the pattern.
 // Assume there won’t be any duplicate characters in the pattern.

// Another solution to the same problem is posted here.

// Examples:

// Input: string = "engineers rock", pattern = "er";
// Output: true
// All 'e' in the input string are before all 'r'.

// Input: string = "engineers rock", pattern = "egr";
// Output: false
// There are two 'e' after 'g' in the input string.

// Input: string = "engineers rock", pattern = "gsr";
// Output: false
// There are one 'r' before 's' in the input string.

///Analysis
/// in the string if last occurance of (n-1)th char in pattern is < first and last occurance of nth char in pattern then the string satisfies the pattern
/// if pattern's length is m and string size is n this algorithm has runtime of O(mn)

function match(str,ptn) {
	var last_char_max_idx=-1, cur_char_max_idx=-1, cur_char_min_idx = -1;
	var is_a_match=true;
	last_char_max_idx = findLastOccuranceIndexInString(str,ptn[0]);
	for(i=1;i<ptn.length;i++) {
		cur_char_max_idx=findLastOccuranceIndexInString(str,ptn[i]);
		cur_char_min_idx=findFirstOccuranceIndexInString(str,ptn[i]);
		if(last_char_max_idx < cur_char_max_idx && last_char_max_idx < cur_char_min_idx) {
			is_a_match = true;
		}
		else {
			is_a_match = false;
		}
		last_char_max_idx = cur_char_max_idx;
		if(is_a_match == false)
			break;
	}
	return is_a_match;
}

function findLastOccuranceIndexInString(str,chr) {
	var curIdx=99999999,maxIdx=-1;
	for(j=0;j<str.length;j++) {
		if(chr == str[j]) {
			curIdx = j;
			if(curIdx > maxIdx) 
				maxIdx = curIdx;
		}
	}
	return maxIdx;
}

function findFirstOccuranceIndexInString(str,chr) {
	var curIdx=99999999,minIdx=999999999;
	for(k=0;k<str.length;k++) {
		if(chr == str[k]) {
			curIdx = k;
			if(curIdx < minIdx) 
				minIdx = curIdx;
		}
	}
	return minIdx;
}



/////////////////////////////////
//////Validation
/////////////////////////////////

console.log(match("engineers rock","er"));
console.log(match("engineers rock","egr"));
console.log(match("engineers rock","gsr"));

///////////////////////////////////
////// personal examples
///////////////////////////////////
console.log(match("engineers rock","ir")); //should be true
console.log(match("engineers rock","ri")); //should be false r comes after i but  in pattern r comes before