Leetcode 2085: Count Common Words With One Occurrence

In this Leetcode problem, we want to know which word occurs exactly once in each of the 2 lists of words provided.

Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays.

These are the couple of examples provided:

Examples and contraints

Solution idea

The main idea to solve this problem is to build a state graph, so that we know what to do with a word that we encounter. We will use HashSet data structure to store the words in the 3 sets that are not the initial “unknown” state, which contain all the other words.

This is how we represent the problem:

State representation of the problem

When going through the first word list, we first add words to the top left state. However, if we encounter a word more than once, it goes to the trash, the bottom right state, and stays there forever!

When traversing the second word list, we put the words from the top left state to the top right state. If we encounter them again, we discard them of course, by putting them in the bottom right state.