You are given a string s and a list dictionary[] of words. Your task is to determine whether the string s can be formed by concatenating one or more words from the dictionary[].
Note: From dictionary[], any word can be taken any number of times and in any order.
Examples :
Input: s= "ilike", dictionary[] = ["i", "like", "gfg"]
Output: true Explanation: s can be breakdown as "i like".
Input: s= "ilikegfg", dictionary[] = ["i", "like", "man", "india", "gfg"] Output: true Explanation: s can be breakdown as "i like gfg".
Input: s= "ilikemangoes", dictionary[] = ["i", "like", "man", "india", "gfg"] Output: false Explanation: s cannot be formed using dictionary[] words.
Constraints:
1 ≤ s.size() ≤ 3000
1 ≤ dictionary.size() ≤ 1000
1 ≤ dictionary[i].size() ≤ 100
Approach 01:
-
C++
-
Python
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Solution {
public:
bool wordBreak(string s, vector<string>& dictionary) {
unordered_set<string> wordSet(dictionary.begin(), dictionary.end());
int strLength = s.length();
vector<bool> canSegment(strLength + 1, false);
canSegment[0] = true; // Base case: empty string can be segmented
int maxWordLength = 0;
if (!dictionary.empty()) {
maxWordLength = max_element(dictionary.begin(), dictionary.end(),
[](const string& a, const string& b) { return a.length() < b.length(); })
->length();
}
for (int end = 1; end <= strLength; ++end) {
for (int start = max(0, end - maxWordLength); start < end; ++start) {
if (canSegment[start] && wordSet.count(s.substr(start, end - start))) {
canSegment[end] = true;
break;
}
}
}
return canSegment[strLength];
}
};
Time Complexity:
- Preprocessing Dictionary:
Building the
unordered_setfrom the dictionary takes \( O(n) \), where \( n \) is the number of words in the dictionary. - Finding Maximum Word Length:
Finding the longest word in the dictionary takes \( O(n) \).
- Dynamic Programming:
For each position \( end \) in the string (up to \( m \)), we check up to \( L \) previous positions, leading to a worst-case time complexity of \( O(mL) \), where \( m \) is the length of the input string and \( L \) is the length of the longest word in the dictionary.
- Substring Lookup:
Checking if a substring exists in the set takes \( O(1) \) on average but \( O(L) \) in the worst case.
- Total Time Complexity:
The overall time complexity is \( O(mL + n) \).
Space Complexity:
- Dictionary Storage:
Storing all words in the
unordered_settakes \( O(nL) \) space in the worst case. - DP Array:
The
canSegmentarray requires \( O(m) \) space. - Total Space Complexity:
The overall space complexity is \( O(m + nL) \).
from typing import List
class Solution:
def wordBreak(self, s: str, dictionary: List[str]) -> bool:
wordSet = set(dictionary)
strLength = len(s)
canSegment = [False] * (strLength + 1)
canSegment[0] = True
maxWordLength = max((len(word) for word in dictionary), default=0)
for end in range(1, strLength + 1):
for start in range(max(0, end - maxWordLength), end):
if canSegment[start] and s[start:end] in wordSet:
canSegment[end] = True
break
return canSegment[strLength]
Time Complexity:
- Preprocessing Dictionary:
Building the
setfrom the dictionary takes \( O(n) \), where \( n \) is the number of words in the dictionary. - Finding Maximum Word Length:
Finding the longest word in the dictionary takes \( O(n) \).
- Dynamic Programming:
For each position \( end \) in the string (up to \( m \)), we check up to \( L \) previous positions, leading to a worst-case time complexity of \( O(mL) \), where \( m \) is the length of the input string and \( L \) is the length of the longest word in the dictionary.
- Substring Lookup:
Checking if a substring exists in the set takes \( O(1) \) on average but \( O(L) \) in the worst case.
- Total Time Complexity:
The overall time complexity is \( O(mL + n) \).
Space Complexity:
- Dictionary Storage:
Storing all words in the
settakes \( O(nL) \) space in the worst case. - DP Array:
The
canSegmentarray requires \( O(m) \) space. - Total Space Complexity:
The overall space complexity is \( O(m + nL) \).