Regular Expression Matching

Definition

Definition

The Regular Expression Matching is a computational method used to determine whether a given string matches a pattern defined by a regular expression. It involves parsing the regular expression and the input string, and then applying matching rules iteratively to determine if there's a match.

Explanation

Starts by parsing the regular expression and the input string. Then, it iterates through each character in the input string and matches it with the corresponding regular expression pattern. It uses techniques like backtracking and dynamic programming to handle complex patterns efficiently

Guidance

• Parse the regular expression into a data structure that represents its components (e.g., characters, wildcards, quantifiers)
• Iterate through each character in the input string
• For each character, compare it with the corresponding pattern in the regular expression
• Apply matching rules based on the pattern, considering characters, wildcards, and quantifiers
• If a match is found, move to the next character in both the input string and the regular expression
• If a mismatch occurs, backtrack or try alternative paths if applicable
• Continue this process until the end of the input string is reached or a match is found

Tips

• implement techniques like memoization to avoid redundant computations
• handle special cases efficiently, such as empty strings and complex patterns with nested quantifiers

Practice

Practice

isMatch(input: string, pattern: string) -> boolean:
  # Start matching from the beginning of input and pattern
  return matchHelper(0, 0)

# Function to recursively match the pattern with the input string
function matchHelper(inputIndex: integer, patternIndex: integer) -> boolean:
  # Base case: both input and pattern are exhausted
  if inputIndex == length(input) and patternIndex == length(pattern):
    return true
  # Base case: pattern is exhausted, but input is not
  if patternIndex == length(pattern):
    return false
  # Check if the current characters match or pattern has wildcard
  currentMatch = inputIndex < length(input) and (input[inputIndex] == pattern[patternIndex] or pattern[patternIndex] == '.')
  # Check if next character in pattern is a quantifier
  if patternIndex + 1 < length(pattern) and pattern[patternIndex + 1] == '*':
    # If pattern has a wildcard, try matching input with pattern after wildcard
    return matchHelper(inputIndex, patternIndex + 2) or (currentMatch and matchHelper(inputIndex + 1, patternIndex))
  # If characters match, move to next character in both input and pattern
  if currentMatch:
    return matchHelper(inputIndex + 1, patternIndex + 1)
  return false

Solution

package main

func regularExpressionMatching(str string, pattern string) bool {
	prevRow := make([]bool, len(pattern)+1)
	currentRow := make([]bool, len(pattern)+1)

	prevRow[0] = true

	for j := 1; j <= len(pattern); j++ {
		if pattern[j-1] == '*' {
			currentRow[j] = prevRow[j-2]
		}
	}

	for i := 1; i <= len(str); i++ {
		nextRow := make([]bool, 1)
		for j := 1; j <= len(pattern); j++ {
			if pattern[j-1] == '*' {
				if prevRow[j] || (j > 1 && currentRow[j-2] && (pattern[j-2] == str[i-1] || pattern[j-2] == '.')) {
					currentRow[j] = true
				} else {
					currentRow[j] = false
				}
			} else if pattern[j-1] == str[i-1] || pattern[j-1] == '.' {
				currentRow[j] = prevRow[j-1]
			} else {
				currentRow[j] = false
			}
			nextRow = append(nextRow, currentRow[j])
		}
		copy(prevRow, currentRow)
		currentRow = nextRow
	}

	return prevRow[len(pattern)]
}

public class Main {

  public static boolean regularExpressionMatching(String str, String pattern) {
    boolean[] prevRow = new boolean[pattern.length() + 1];
    boolean[] currentRow = new boolean[pattern.length() + 1];

    prevRow[0] = true;

    for (int j = 1; j <= pattern.length(); j++) {
      if (pattern.charAt(j - 1) == '*') {
        currentRow[j] = prevRow[j - 2];
      }
    }

    for (int i = 1; i <= str.length(); i++) {
      boolean[] nextRow = new boolean[1];
      for (int j = 1; j <= pattern.length(); j++) {
        if (pattern.charAt(j - 1) == '*') {
          if (prevRow[j] || (j > 1 && currentRow[j - 2] && (pattern.charAt(j - 2) == str.charAt(i - 1) || pattern.charAt(j - 2) == '.'))) {
            currentRow[j] = true;
          } else {
            currentRow[j] = false;
          }
        } else if (pattern.charAt(j - 1) == str.charAt(i - 1) || pattern.charAt(j - 1) == '.') {
          currentRow[j] = prevRow[j - 1];
        } else {
          currentRow[j] = false;
        }
        nextRow = Arrays.copyOf(nextRow, nextRow.length + 1);
        nextRow[nextRow.length - 1] = currentRow[j];
      }
      System.arraycopy(currentRow, 0, prevRow, 0, prevRow.length);
      currentRow = nextRow;
    }

    return prevRow[pattern.length()];
  }
}

function regularExpressionMatching(string, pattern) {
  const prevRow = Array(pattern.length + 1).fill(false);
  let currentRow = Array(pattern.length + 1).fill(false);

  prevRow[0] = true;

  for (let j = 1; j <= pattern.length; j++) {
    if (pattern[j - 1] === "*") {
      currentRow[j] = prevRow[j - 2];
    }
  }

  for (let i = 1; i <= string.length; i++) {
    const nextRow = [false];
    for (let j = 1; j <= pattern.length; j++) {
      if (pattern[j - 1] === "*") {
        if (
          prevRow[j] ||
          (j > 1 &&
            currentRow[j - 2] &&
            (pattern[j - 2] === string[i - 1] || pattern[j - 2] === "."))
        ) {
          currentRow[j] = true;
        } else {
          currentRow[j] = false;
        }
      } else if (pattern[j - 1] === string[i - 1] || pattern[j - 1] === ".") {
        currentRow[j] = prevRow[j - 1];
      } else {
        currentRow[j] = false;
      }
      nextRow.push(currentRow[j]);
    }
    prevRow.splice(0, prevRow.length, ...currentRow);
    currentRow = nextRow;
  }

  return prevRow[pattern.length];
}

fun regularExpressionMatching(str: String, pattern: String): Boolean {
    var prevRow = BooleanArray(pattern.length + 1)
    var currentRow = BooleanArray(pattern.length + 1)

    prevRow[0] = true

    for (j in 1..pattern.length) {
        if (pattern[j - 1] == '*') {
            currentRow[j] = prevRow[j - 2]
        }
    }

    for (i in 1..str.length) {
        var nextRow = booleanArrayOf()
        for (j in 1..pattern.length) {
            if (pattern[j - 1] == '*') {
                if (prevRow[j] || (j > 1 && currentRow[j - 2] && (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.'))) {
                    currentRow[j] = true
                } else {
                    currentRow[j] = false
                }
            } else if (pattern[j - 1] == str[i - 1] || pattern[j - 1] == '.') {
                currentRow[j] = prevRow[j - 1]
            } else {
                currentRow[j] = false
            }
            nextRow += currentRow[j]
        }
        prevRow = currentRow.copyOf()
        currentRow = nextRow.toBooleanArray()
    }

    return prevRow[pattern.length]
}

def regular_expression_matching(string, pattern):
    prev_row = [False] * (len(pattern) + 1)
    current_row = [False] * (len(pattern) + 1)

    prev_row[0] = True

    for j in range(1, len(pattern) + 1):
        if pattern[j - 1] == '*':
            current_row[j] = prev_row[j - 2]

    for i in range(1, len(string) + 1):
        next_row = [False]
        for j in range(1, len(pattern) + 1):
            if pattern[j - 1] == '*':
                if prev_row[j] or (j > 1 and current_row[j - 2] and (pattern[j - 2] == string[i - 1] or pattern[j - 2] == '.')):
                    current_row[j] = True
                else:
                    current_row[j] = False
            elif pattern[j - 1] == string[i - 1] or pattern[j - 1] == '.':
                current_row[j] = prev_row[j - 1]
            else:
                current_row[j] = False
            next_row.append(current_row[j])
        prev_row = current_row[:]
        current_row = next_row

    return prev_row[len(pattern)]

fn regular_expression_matching(string: &str, pattern: &str) -> bool {
    let mut prev_row = vec![false; pattern.len() + 1];
    let mut current_row = vec![false; pattern.len() + 1];

    prev_row[0] = true;

    for j in 1..=pattern.len() {
        if pattern.chars().nth(j - 1) == Some('*') {
            current_row[j] = prev_row[j - 2];
        }
    }

    for (i, ch) in string.chars().enumerate() {
        let mut next_row = vec![false; 1];
        for j in 1..=pattern.len() {
            if pattern.chars().nth(j - 1) == Some('*') {
                if prev_row[j] || (j > 1 && current_row[j - 2] && (pattern.chars().nth(j - 2) == Some(ch) || pattern.chars().nth(j - 2) == Some('.'))) {
                    current_row[j] = true;
                } else {
                    current_row[j] = false;
                }
            } else if pattern.chars().nth(j - 1) == Some(ch) || pattern.chars().nth(j - 1) == Some('.') {
                current_row[j] = prev_row[j - 1];
            } else {
                current_row[j] = false;
            }
            next_row.push(current_row[j]);
        }
        prev_row = current_row.clone();
        current_row = next_row;
    }

    prev_row[pattern.len()]
}

function regularExpressionMatching(string: string, pattern: string): boolean {
  let prevRow: boolean[] = new Array<boolean>(pattern.length + 1).fill(false);
  let currentRow: boolean[] = new Array<boolean>(pattern.length + 1).fill(
    false,
  );

  prevRow[0] = true;

  for (let j = 1; j <= pattern.length; j++) {
    if (pattern[j - 1] === "*") {
      currentRow[j] = prevRow[j - 2];
    }
  }

  for (let i = 1; i <= string.length; i++) {
    let nextRow: boolean[] = [false];
    for (let j = 1; j <= pattern.length; j++) {
      if (pattern[j - 1] === "*") {
        if (
          prevRow[j] ||
          (j > 1 &&
            currentRow[j - 2] &&
            (pattern[j - 2] === string[i - 1] || pattern[j - 2] === "."))
        ) {
          currentRow[j] = true;
        } else {
          currentRow[j] = false;
        }
      } else if (pattern[j - 1] === string[i - 1] || pattern[j - 1] === ".") {
        currentRow[j] = prevRow[j - 1];
      } else {
        currentRow[j] = false;
      }
      nextRow.push(currentRow[j]);
    }
    prevRow.splice(0, prevRow.length, ...currentRow);
    currentRow = nextRow;
  }

  return prevRow[pattern.length];
}