FastPrep
Problem · String

Simulate a Deterministic Finite Automaton

Learn this problem
● EasyPoint72 logoPoint72FULLTIMEOA

Problem 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 reading a.
  • transitions[s][1] is the next state after reading b.

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[]) → boolean

Examples

Example 1

input = "abba"transitions = [[1,0],[1,0]]startState = 0acceptingStates = [1]return = true

The 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 = false

Every b transition keeps the automaton at state 0, which is not accepting.

Example 3

input = ""transitions = [[0,0]]startState = 0acceptingStates = [0]return = true

The empty input leaves the automaton at its accepting start state.

Constraints

  • 1 <= transitions.length <= 100000
  • transitions[s].length == 2 for every state s.
  • Every transition destination, startState, and accepting state is between 0 and transitions.length - 1.
  • 0 <= input.length <= 100000
  • input contains only a and b.
  • acceptingStates contains distinct state numbers.

More Point72 problems

drafts saved locally
public boolean acceptsDFA(String input, int[][] transitions, int startState, int[] acceptingStates) {
  // write your code here
}
input"abba"
transitions[[1,0],[1,0]]
startState0
acceptingStates[1]
expectedtrue
checking account