Count Spellings Using Chemical Element Symbols
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Count Spellings Using Chemical Element Symbols
## Problem
Given a list of valid chemical element symbols and a target word, count how many distinct ways the entire word can be segmented into symbols. Matching is case-insensitive, symbols may be reused, and different boundary placements count as different spellings.
Implement:
```python
def count_symbol_spellings(symbols: list[str], word: str) -> int:
...
```
The input symbol list is the complete source of truth; the function must not rely on a built-in periodic table.
## Constraints
- `1 <= len(symbols) <= 200`
- Every symbol contains one or two ASCII letters.
- Symbols are unique under case-insensitive comparison.
- `0 <= len(word) <= 100_000`
- `word` contains only ASCII letters.
- Return an arbitrary-precision integer.
- The empty word has one valid spelling: choose no symbols.
## Example
```python
symbols = ["P", "H", "Y", "Si", "C", "S", "Cs", "I"]
count_symbol_spellings(symbols, "Physics")
```
The result is `4`, corresponding to these boundary choices:
```text
P-H-Y-Si-C-S
P-H-Y-Si-Cs
P-H-Y-S-I-C-S
P-H-Y-S-I-Cs
```
## Performance Goal
Avoid enumerating and storing every complete spelling. State the time and auxiliary-space complexity of your approach.
Overview: Count how many ways a word can be segmented into supplied one- or two-letter chemical element symbols. Design a case-insensitive dynamic program that supports symbol reuse, arbitrary-precision counts, and a 100,000-character target without enumerating spellings.
Read the full Google Software Engineer interview experience this question came from
Count the distinct full segmentations of a word into supplied one- or two-letter chemical symbols. Matching is case-insensitive, symbols may be reused, and boundary choices distinguish spellings.
Constraints
- There are at most 200 unique case-insensitive symbols.
- Each symbol contains one or two ASCII letters.
- The word contains only ASCII letters and may have length 100,000.
- The empty word has one spelling.
Examples
Input: {'symbols':['P','H','Y','Si','C','S','Cs','I'],'word':'Physics'}
Expected Output: 4
Explanation: The supplied word has four boundary patterns.
Input: {'symbols':['A','Aa'],'word':'aaa'}
Expected Output: 3
Explanation: One- and two-letter choices yield three segmentations.
Hints
- Dynamic programming needs only the counts one and two positions back.
- Normalize both symbols and word to one case once.
Community answers
Answer by selenewang941015
def count_segmentations(symbols, word):
symbols = {s.lower() for s in symbols}
word = word.lower()
n = len(word)
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
if word[i - 1:i] in symbols:
dp[i] += dp[i - 1]
if i >= 2 and word[i - 2:i] in symbols:
dp[i] += dp[i - 2]
return dp[n]
Answer by Josef420
from functools import cache
def count_symbol_spellings(symbols, word):
if not symbols and not word:
return 1
symbols_set = set(sym.lower() for sym in symbols)
max_sym_len = max([len(sym) for sym in symbols])
word = word.lower()
@cache
def dp(index: int = 0):
if index == len(word):
return 1
total_count: int = 0
print(index)
for next_idx in range(index, min(len(word), index + max_sym_len)):
next_split = word[index:next_idx+1]
print(next_split)
if next_split not in symbols_set:
continue
total_count += dp(next_idx+1)
return total_count
return dp()