# Problem Statement
You are given a dictionary of words and a large input string. You have to find out whether the input string can be completely segmented into the words of a given dictionary. The following two examples elaborate on the problem further.

<br>

## Hint
* Memoization

<br>

## Try it yourself

def can_segment_string(s, dictionary):
  #TODO: Write - Your - Code
  return False

Python

class StringSegmentation{
  public static boolean canSegmentString(String s, Set<String> dictionary) {
    //TODO: Write - Your - Code
    return false;
  }
} 

Java

bool canSegmentString(string s, unordered_set<string> &dictionary) {
  //TODO: Write - Your - Code
  return false;
}

#include <string>
#include <unordered_set>
#include <iostream>
using namespace std;

let canSegmentString = function(s, dictionary) {
  //TODO: Write - Your - Code
  return false;
};

JavaScript

def can_segment_string(s, dictionary)
  #TODO: Write - Your - Code
  return false
end

Ruby

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")

import java.util.HashSet;
import java.util.Set;

class StringSegmentation {

    public static boolean canSegmentString(String s, Set<String> dictionary) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;  // Empty string can be segmented

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dictionary.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        Set<String> dictionary = new HashSet<>();
        String s = "hellonow";

        dictionary.add("hello");
        dictionary.add("hell");
        dictionary.add("on");
        dictionary.add("now");
        if (canSegmentString(s, dictionary)) {
            System.out.println("String Can be Segmented");
        } else {
            System.out.println("String Can NOT be Segmented");
        }
    }
}

#include <iostream>
#include <unordered_set>
#include <vector>
#include <string>

using namespace std;

bool canSegmentString(string s, unordered_set<string> &dictionary) {
    int n = s.length();
    vector<bool> dp(n + 1, false);
    dp[0] = true; // Empty string can be segmented

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dictionary.find(s.substr(j, i - j)) != dictionary.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

int main() {
  string s = "hellonow";
  unordered_set <string> dictonary = { "hello", "hell", "on", "now" };
  if (canSegmentString(s, dictonary))
    cout << "String Can be Segmented" << endl;
  else
    cout << endl << "String Can NOT be Segmented" << endl;
  return 0;
}

require 'set'

def can_segment_string(s, dictionary)
  n = s.length
  dp = Array.new(n + 1, false)
  dp[0] = true  # Empty string can be segmented

  for i in 1..n
    for j in 0...i
      if dp[j] && dictionary.include?(s[j...i])
        dp[i] = true
        break
      end
    end
  end

  return dp[n]
end

s = "hellonow"
dictionary = Set.new(["hello","hell","on","now"])

if can_segment_string(s, dictionary)
  puts "String Can be Segmented"
else
  puts "String Can NOT be Segmented"
end

## Solution Explanation
### Runtime Complexity
The runtime complexity of this solution is polynomial, $O(n^3)$.


### Memory Complexity
The memory complexity of this solution is linear, $O(n)$.

<br>

### 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.
1. 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.
2. Set `dp[0]` to TRUE to indicate that the empty string can be segmented.
3. Iterate over the indexes of the word from 1 to `n`.
4. 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.
5. After completing the iterations, return `dp[n]` to indicate whether the entire word can be segmented.

> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Given a dictionary of words and an input string tell whether the input string can be completely segmented into dictionary words.

String Segmentation

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown