Good Maker
BAN USERAttached below the detailed code and algorithm with explanation, it covers all of the mentioned cases ...
<script>
function checkMatching(sourceStr, patternStr) {
return isMatching(sourceStr, patternStr, sourceStr.length - 1, patternStr.length - 1);
}
/*
* Algorithm is very simple:
* 1. Iterate on every pattern and source string from right to left.
* 2. If you find a matching character between pattern and source then decrease the pointer of both source and pattern (sourceIndex and patternIndex) by 1.
* 3. If you do not find a matching character then check if the current pattern character is '*', and if it is '*' then compare the pattern character before the '*' with the source character:
* 3.1. If you find a matching then decrement source index by 1.
* 3.2. If you do not find a matching then decrement pattern index by 2 which means that the source character is not in the indicated pattern.
* 4. Finally, if you find the source string already consumed (sourceIndex < 0) and there are already existing characters in the pattern string then check that the remaining characters are all following <char>* pattern in order to have a correct matching other than this return false.
*/
function isMatching(sourceStr, patternStr, sourceIndex, patternIndex) {
if (patternStr == '*') {
return true;
}
if (sourceIndex < 0 && patternIndex < 0) {
return true;
} else if (sourceIndex < 0) {
//Check if the remaining parts of the pattern are not optional
while (patternIndex >= 0) {
if (patternStr.charAt(patternIndex) == '*') {
patternIndex = patternIndex - 2;
} else {
return false;
}
}
return true;
}
if (sourceStr.charAt(sourceIndex) == patternStr.charAt(patternIndex)) {
return isMatching(sourceStr, patternStr, --sourceIndex, --patternIndex);
} else if (patternStr.charAt(patternIndex) == '*') {
if (sourceStr.charAt(sourceIndex) == patternStr.charAt(patternIndex - 1)) {
return isMatching(sourceStr, patternStr, --sourceIndex, patternIndex);
} else {
patternIndex -= 2;
return isMatching(sourceStr, patternStr, sourceIndex, patternIndex);
}
} else {
return false;
}
}
console.log(checkMatching("aa", "a")); //false
console.log(checkMatching("aa", "aa")); //true
console.log(checkMatching("aa", "a*")); //true
console.log(checkMatching("aa", "*")); //true
console.log(checkMatching("a", "b*a")); //true
console.log(checkMatching("a", "a*a")); //true
console.log(checkMatching("a", "b*a*a")); //true
console.log(checkMatching("aab", "c*a*b")); //true
console.log(checkMatching("ccccccaaab", "c*a*b")); //true
console.log(checkMatching("ccccccb", "c*a*b")); //true
console.log(checkMatching("ccccccb", "c*a*b")); //true
console.log(checkMatching("bz", "c*a*bz")); //true
console.log(checkMatching("ccccb", "w*c*a*b")); //true
console.log(checkMatching("wz", "w*c*a*b")); //false
</script>
Very simple problem. This is the JavaScript solution, whose worst case performance is o(n).
<script>
function isSubString(sourceStr, subStr, sourceIndex, subStrIndex) {
if (sourceIndex >= sourceStr.length) {
return -1;
}
if (subStrIndex >= subStr.length) {
var res = sourceStr.substr(0, sourceIndex - (subStr.length - 1));
if (sourceIndex < sourceStr.length - 1) {
res += sourceStr.substr(sourceIndex + 1);
}
return res;
}
++ sourceIndex;
if (sourceStr.charAt(sourceIndex) == subStr.charAt(subStrIndex)) {
++subStrIndex;
return isSubString(sourceStr, subStr, sourceIndex, subStrIndex);
} else {
return isSubString(sourceStr, subStr, sourceIndex, 0);
}
}
alert(isSubString("xabc", "abc", 0, 0)); //x
alert(isSubString("ababbabcd", "abc", 0, 0)); //ababbd
alert(isSubString("ababbabcd", "abd", 0, 0)); //-1
alert(isSubString("ababbabcd", "bcd", 0, 0)); //ababba
alert(isSubString("ababbabcd", "ccd",0, 0)); //-1
alert(isSubString("ababbabcd", "bba", 0, 0)); //ababcd
</script>
This is my solution to the problem.
- Good Maker August 14, 2015