CODEWITHSUNDEEP
pythonstring
Harish
Harish

Reputation: 368

Merge strings with common last and first word

Given input as a list of strings

input = [
'mission statement',
'a quick bite to eat',
'a chip off the old block',
'chocolate bar',
'mission impossible',
'a man on a mission',
'block party',
'eat my words',
'bar of soap'
]

I need to write a function which would combine a pair of strings which have common last and first word as S1 + S2

Ex: 'a man on a mission', -> S1 'mission statement' -> S2

Then it would output 'a man on a mission statement'

Output for the above list of strings is

output = [
'a quick bite to eat my words',
'a chip off the old block party',
'chocolate bar of soap',
'a man on a mission statement',
'a man on a mission impossible'
]

This is my piece of code in python

firstMapper = {}

for val in input:
    wordList = val.split()
    firstMapper[wordList[0]] = ' '.join([str(x) for x in wordList[1:]])

ans = []

for val in input:
    wordList = val.split()
    if wordList[-1] in firstMapper:
        k = val+" "+firstMapper[wordList[-1]]
        if k not in ans:
            ans.append(k)

print(ans)

but this gives me only

['a quick bite to eat my words', 'a chip off the old block party', 'chocolate bar of soap', 'a man on a mission impossible']

I need this to be done in O(n)

Update

I managed to do it in this way

firstMapper = {}

for val in input:
    wordList = val.split()
    if wordList[0] in firstMapper:
        firstMapper[wordList[0]].append(' '.join(wordList[1:]))
    else:
        temp = []
        temp.append(' '.join(wordList[1:]))
        firstMapper[wordList[0]] = temp

ans = []

for val in input:
    wordList = val.split()
    if wordList[-1] in firstMapper:
        k = list(map(lambda x : val+" "+x, firstMapper[wordList[-1]]))
        if k not in ans:
            ans.extend(k)

print(ans)

Can this be solved in a better way?

Upvotes: 1

Views: 841

Answers (1)

gahooa
gahooa

Reputation: 137322

The following code does what you want. Here is a description of the functionality:

  • Use collections.defaultdict to facilitate creating a mapping of string to list
  • Create a map of all first words -> list of phrases
  • Create a map of all last word -> list of phrases
  • Use the excellent set type to intersect the keys of these two mappings to find out which ones are in common.
  • Generate the product of both lists where the words are in common

It is approximately O(n) because of a single pass over the data, and then use of the blindingly fast set type.

from collections import defaultdict

data = [
  'mission statement',
  'a quick bite to eat',
  'a chip off the old block',
  'chocolate bar',
  'mission impossible',
  'a man on a mission',
  'block party',
  'eat my words',
  'bar of soap'
  ]

last_word_map = defaultdict(list)
first_word_map = defaultdict(list)

for phrase in data:
  words = phrase.split()
  last_word_map[words[-1]].append(' '.join(words[0:-1]))
  first_word_map[words[0]].append(' '.join(words[1:]))

first_word_set = set(first_word_map)
last_word_set = set(last_word_map)

shared_set = set(first_word_map).intersection(last_word_map)

for shared_word in shared_set:
  for last_part in first_word_map[shared_word]:
    for first_part in last_word_map[shared_word]:
      print(first_part + ' ' + shared_word + ' ' + last_part)

Output is:

a chip off the old block party
a quick bite to eat my words
a man on a mission statement
a man on a mission impossible
chocolate bar of soap

Upvotes: 1

Related Questions