Finite Automata String Matching | Dataford Interview Questions

Explain how you would use a deterministic finite automaton to perform string pattern matching that accepts or rejects based on the input.

Write a function that builds or simulates a DFA for a given pattern and returns whether an input text is accepted. Assume the alphabet is lowercase English letters.

Constraints

1 <= len(pattern) <= 10^4
1 <= len(text) <= 10^5
pattern and text contain only lowercase English letters

Function Signature

def dfa_match(pattern, text):

Your question is Finite Automata String Matching. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Explain how you would use a deterministic finite automaton to perform string pattern matching that accepts or rejects based on the input.

Write a function that builds or simulates a DFA for a given pattern and returns whether an input text is accepted. Assume the alphabet is lowercase English letters.

Constraints

1 <= len(pattern) <= 10^4
1 <= len(text) <= 10^5
pattern and text contain only lowercase English letters

Function Signature

def dfa_match(pattern, text):

Your question is Finite Automata String Matching. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.