String Segmentation

Coding Skill Exercise #25

String Segmentation

Write a method that segments a given string. The parameters to the method are the string, a set containing words.

Example

Input : applepie Output : apple pie

Set dictionary consists of apple, pear, pier, pie.

Knowledge Gap Finder

If you are unable to code the solution, answer the following questions and reply to this email to get customized lesson.

Was the problem statement clear to you when you read it? What did you think of doing first? Were you reminded of a construct in general or a general structure of solution that you thought would be useful? Have you previously seen problems that resemble this one? Did you feel stuck at any point while working on this problem? What did you choose as your test case? Do you think you’ve covered all possible scenarios with your tests? What program design techniques did you apply to solve this problem? Are there any constructs of the programming language that you find difficult or confusing to use? What issues make programming constructs difficult to use? For example, the keyword used, the syntax, the examples, the documentation for the construct, etc.

Feel free to forward this email to your friends so they can subscribe here. https://codingskill.biz

title: String Segmentation excerpt: Solution for a common string interview question using set. tags: return-value-of-recursive-method

The return value of the recursive function is used to calculate the final result. Set is used to keep track of words we have already seen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

require 'set'

def segment_string(s, dictionary, solved)
  for i in (1..s.size)
    first = s[0, i]

    if dictionary.include?(first)
      second = s[i..-1]

      if second.size == 0
        return true
      end
			
      if dictionary.include?(second)
        return true
      end
      
      unless solved.include?(second)
        if segment_string(second, dictionary, solved)
          return true
        end
        
        solved.add(second)
      end
    end
  end
  
  false
end

def can_segment_string?(s, dictionary)
  solved = Set.new
  segment_string(s, dictionary, solved)
end

dictionary = Set['hello', 'hell', 'on', 'now']

p can_segment_string?('hellonow', dictionary)

Building Blocks

• Return Value of Recursive Method