Как найти совпадение слов в двух строках? - PullRequest
Новая
       33

Как найти совпадение слов в двух строках?

0 голосов
/ 06 декабря 2018

У меня есть две строки, такие как

My name is Bogdan и Bogdan and I am from Russia

Мне нужно получить слово Bogdan из этой строки.Я всегда знаю, какой конец первого предложения == начало второго предложения.

Как мне найти это перекрытие.

Мое решение возвращает похожие символы 

res = list(set('My name is Bogdan').intersection(set('Bogdan and i am from Russia')))
print(res)

Возвращает 

['i', 'n', 'g', 'm', ' ', 's', 'B', 'a', 'd', 'o']

Ответы [ 3 ]

0 голосов
/ 06 декабря 2018

Можно использовать набор пересечения 

l1="My name is Bogdan"
l2="Bogdan and I am from Russia"
print(set(l1.split())&set(l2.split())) # set('Bogdan')

Понимание списка 

l1="My name is Bogdan"
l2="Bogdan and I am from Russia"
[i for i in l1.split() if i in l2.split()] ['Bogdan']
0 голосов
/ 06 декабря 2018

Другой вариант, с циклом for: 

def shared_words(s1, s2):
  res = []
  l_s1, l_s2 = set(s1.split()), set(s2.split())
  for ss1 in l_s1:
    if ss1 in l_s2: res.append(ss1)
  return res

Применить к строке: 

s1 = "My name is Bogdan"
s2 = "Bogdan and I am from Russia"
print(shared_words(s1, s2)) #=> ['Bogdan']

Или, используя регулярное выражение для разделения только слов: 

import re

def shared_words(s1, s2):
  res = []
  l_s1, l_s2 = set(re.findall(r'\w+',s1)), set(re.findall(r'\w+',s2))
  for ss1 in l_s1:
    if ss1 in l_s2: res.append(ss1)
  return res

Чтобы получить: 

s1 = "My name is Bogdan, I am here"
s2 = "Bogdan and I am from Russia."
print(shared_words(s1, s2)) #=> ['Bogdan', 'I', 'am']
0 голосов
/ 06 декабря 2018

Вы начинаете с максимального перекрытия двух строк, а затем выполняете итерацию, уменьшая перекрытие: 

def find_overlap(s1, s2):
    for i in range(len(s1)):
        test1, test2 = s1[i:], s2[:len(s1) - i]
        if test1 == test2:
            return test1

s1, s2 = "My name is Bogdan", "Bogdan and I am from Russia"
find_overlap(s1, s2)
# 'Bogdan'
s1, s2 = "mynameisbogdan", "bogdanand"
find_overlap(s1, s2)
# 'bogdan'

Как вы можете видеть, это также работает, если две строки не содержат пробелов.

Это имеет время выполнения O (n), но может быть уменьшено до O (min (n, m)), если вы сначала определите, какая из двух строк короче.

Если вы ожидаете, что строка окажется намногокороче, чем даже самая короткая из двух строк, вы можете сделать это даже O (k), где k - длина строки, которую нужно найти, начиная с минимального перекрытия: 

def find_overlap(s1, s2):
    for i in range(1, len(s1) + 1):
        if i == len(s2):
            return None
        test1, test2 = s1[-i:], s2[:i]
        if test1 == test2:
            return test1
...