educative.io

Memo + String Scan (no recursion)

Courses
, ,
#1

Am I missing something? It passes the test cases and looks like it’s O(n+m).
First create a memo mapping word len to words in dict; then scan the string and build up the “current” string. If it’s too short, move on. Too long and we know we’re out of the dictionary. If the length is within the memo, then check if the word is in that set of words with the same length. If it isn’t, move on. If it is, reset the current string. Then do that check again at the end in case there’s still a current string built out.

def can_segment_string(s, dictionary):
  len_memo = {}
  shortest = None
  longest = None
  # O(len(dictionary))
  for word in list(dictionary):
    wordlen = len(word)
    if shortest == None:
      shortest = wordlen
    else:
      shortest = min(shortest, wordlen)
    if longest == None:
      longest = wordlen
    else:
      longest = max(longest, wordlen)
    if len(word) not in len_memo:
      len_memo[len(word)] = set()
    len_memo[len(word)].add(word)
  # now have inverse, longest & shortest words
  """
  {
    3: {'pie'}
    4: {'pier', 'pear'}
    5: {'apple'}
  }
  """
  # + O(len(s))
  current_len = 0
  current_s = ''
  for i, char in enumerate(s):
    current_len += 1
    current_s += char
    if current_len < shortest:
      continue
    if current_len > longest:
      return False
    if current_len in len_memo and current_s in len_memo[current_len]:
      current_len = 0
      current_s = ''
  if current_len and current_s:
    if not shortest < current_len < longest or current_len not in len_memo or current_s not in len_memo[current_len]:
      return False

  return True
#2

I think this can be solved using O(n). We just start building a subString (from right to left, so that we can form the longest possible i.e. pier vs pie) and see if it is part of dictionary. If yes then we start new word. We can go on till we reach the end of string.

let canSegmentString = function (inputString, dictionary) { let subStr = ''; for (let i = inputString.length - 1; i >= 0; i--) { subStr = inputString[i] + subStr; console.log(subStr, i); if (dictionary.has(subStr)) { subStr = ''; } } return subStr === ''; };