Minimum Dictionary Segments
Updated
Problem statement
Given a string s and an array dictionary, split all of s into a sequence of dictionary words.
Return the minimum possible number of words in a complete split. Return -1 if no complete split exists. The empty string requires zero words.
Function
minimumDictionarySegments(s: String, dictionary: String[]) → intExamples
Example 1
s = "applepie"dictionary = ["apple","app","le","pie"]return = 2The split apple | pie uses two words. No dictionary word covers the entire string.
Example 2
s = "aaaa"dictionary = ["a","aa","aaa"]return = 2Either a | aaa or aaa | a uses the minimum of two words.
Example 3
s = "catsandog"dictionary = ["cats","dog","sand","and","cat"]return = -1Every possible prefix split leaves characters that cannot be covered by a dictionary word.
Constraints
0 <= s.length <= 20000 <= dictionary.length <= 20001 <= dictionary[i].length <= 50sand every dictionary word contain lowercase English letters.- Duplicate dictionary words have no additional effect.
More Google Phone Screen questions
- Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
- Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
- Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
- Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Nested Substitutions with Cycle DetectionKikoff · PHONE SCREENKikoff interview questions
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Edit DistanceAstrotalk · PHONE SCREEN
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Nested Event Group CountsMixpanel · PHONE SCREENMixpanel interview questions
- Nested Set Structural EquivalencePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Longest Substring with At Least K Repeating CharactersBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Can the Text Split Into Dictionary WordsAdobe · PHONE SCREENAdobe interview questions
- Longest Common URL History RunDatadog · PHONE SCREENDatadog interview questions
- Word Break IIWex · PHONE SCREEN