String Segmentation

Home/

Blog/

String Segmentation

1 min read

Oct 15, 2025

Content

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown

def can_segment_string(s, dictionary) -> bool:
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string can be segmented
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in dictionary:
                dp[i] = True
                break 
    return dp[n]
  
s = "hellonow";
dictionary= set(["hello","hell","on","now"])
if can_segment_string(s, dictionary):
  print("String Can be Segmented")
else:
  print("String Can NOT be Segmented")

Solution Explanation#

Runtime Complexity#

The runtime complexity of this solution is polynomial, O(n3)O(n3).

Memory Complexity#

The memory complexity of this solution is linear, O(n)O(n).

Solution Breakdown#

The algorithm iteratively checks substrings of the input string against the dictionary. Starting with an empty string being segmentable, it gradually builds up segmentability information for larger substrings by considering all possible substrings and checking if they exist in the dictionary. Once we determine that a substring can be segmented into words from the dictionary, we mark the corresponding entry in an array dp array as TRUE. Subsequently, when processing longer substrings, we use dp to check whether shorter substrings within them have already been determined to be segmentable, avoiding recomputations.

Initialize a variable n with the length of the input word and create a boolean array dp with a size of n + 1. Initialize all values of dp to FALSE.
Set dp[0] to TRUE to indicate that the empty string can be segmented.
Iterate over the indexes of the word from 1 to n.
For each index i, iterate over the indexes j from 0 to i - 1.
Check if dp[j] is TRUE and if the substring word[j:i] exists in the dictionary.
If both conditions are met, set dp[i] to TRUE.
After completing the iterations, return dp[n] to indicate whether the entire word can be segmented.