Simulate a Deterministic Finite Automaton
Point72● EasyFULLTIMEOAProblem statement
Simulate a deterministic finite automaton and return whether it accepts input.
The automaton has states numbered from 0 through transitions.length - 1. For every state s:
transitions[s][0]is the next state after readinga.transitions[s][1]is the next state after readingb.
Begin at startState and process the characters of input from left to right. Return true if the state reached after the entire string belongs to acceptingStates; otherwise, return false. An empty input performs no transition, so acceptance depends on whether startState is accepting.
Function
acceptsDFA(input: String, transitions: int[][], startState: int, acceptingStates: int[]) → booleanExamples
Example 1
input = "abba"transitions = [[1,0],[1,0]]startState = 0acceptingStates = [1]return = trueThe visited states are 0 -> 1 -> 0 -> 0 -> 1. The final state 1 is accepting.
Example 2
input = "bbb"transitions = [[1,0],[1,0]]startState = 0acceptingStates = [1]return = falseEvery b transition keeps the automaton at state 0, which is not accepting.
Example 3
input = ""transitions = [[0,0]]startState = 0acceptingStates = [0]return = trueThe empty input leaves the automaton at its accepting start state.
Constraints
1 <= transitions.length <= 100000transitions[s].length == 2for every states.- Every transition destination,
startState, and accepting state is between0andtransitions.length - 1. 0 <= input.length <= 100000inputcontains onlyaandb.acceptingStatescontains distinct state numbers.