You are given a list of chemical element symbols and a word. Count the number of different ways to form the entire word by joining symbols from the list.

Symbols may be reused, and matching is case-insensitive. Each character of the word must belong to exactly one selected symbol.

Class

PeriodicTableWordCounter

Method

countWaysToFormWord

long countWaysToFormWord(List<String> elementSymbols, String word)

Parameters

• elementSymbols: The available chemical element symbols.
• word: The word that must be formed.

Returns

Return the number of different sequences of element symbols whose concatenated letters equal word, ignoring letter case. Return 0 if the word cannot be formed.

Rules

• Every selected symbol must match the next one or two letters of the word.
• The same element symbol may be selected more than once.
• Two ways are different if their sequences of selected symbols are different.
• Letter case does not affect matching. For example, "Co" matches "co", "CO", and "Co".
• Every string in elementSymbols is a valid chemical element symbol.

Constraints

• 1 ≤ elementSymbols.size() ≤ 118
• 1 ≤ elementSymbols.get(i).length() ≤ 2
• 1 ≤ word.length() ≤ 90
• elementSymbols contains no duplicates when letter case is ignored.
• elementSymbols and word contain only English letters.
• The answer fits in a signed 64-bit integer.

Examples

Example 1

countWaysToFormWord( elementSymbols = List.of("C", "O", "Co"), word = "CoCo")

Output: 4

The four possible sequences are:

• C - O - C - O
• C - O - Co
• Co - C - O
• Co - Co

Example 2

countWaysToFormWord( elementSymbols = List.of("N", "Ne", "O"), word = "Neon")

Output: 1

The only possible sequence is Ne - O - N.

Example 3

countWaysToFormWord( elementSymbols = List.of("He", "Li", "O"), word = "Hello")

Output: 0

No sequence of the provided element symbols forms the entire word.