Basic regex parser

basic_regex_parser.js

// n - text size, m = patter size
// Time: O(n+m), Space: O(m)
function isMatch(text, pattern) {
  var tokens = tokenize(pattern);
  var textPointer = 0;
  var tokenPointer = 0;
  
  while (tokenPointer < tokens.length) {
    var token = tokens[tokenPointer];
    var char = findChar(text, textPointer);
  
    if (token.isStar) {
      if (token.value === '.') {
        if (char === '') {
          tokenPointer++;
        } else {
          token.value = char;
          tokenPointer++;
          textPointer++;
        }
      } else {
        if (char === token.value) {
          textPointer++;
        } else {
          tokenPointer++;
        }
      }
    } else if (token.value === '.' || token.value === char) {
      tokenPointer++;
      textPointer++;
    } else {
      return false;
    }
  }

  return findChar(text, textPointer) === '';
}

function findChar(text, i) {
  if (i >= text.length) {
    return '';
  }
  
  return text[i];
}
     

function tokenize(pattern) {
  var tokens = [];
  
  for (var i = 0; i < pattern.length; i++) {
    if (pattern[i] === '*') {
      tokens[tokens.length - 1].isStar = true;
    } else {
      tokens.push({ value: pattern[i], isStar: false });
    }
  }
  
  return tokens;
}