我尝试将所需的解码算法问题分解为更小的问题。这是第一部分。
问题:
示例1:
s1 = "12 November 2010 - 1 visitor"
s2 = "6 July 2010 - 100 visitors"
the identical parts are "2010", "-", "1" and "visitor"
示例2:
s1 = "Welcome, John!"
s2 = "Welcome, Peter!"
the identical parts are "Welcome," and "!"
示例 3:(澄清“!”示例)
s1 = "Welcome, Sam!"
s2 = "Welcome, Tom!"
the identical parts are "Welcome," and "m!"
Python 和 Ruby 优先。谢谢
编辑:更新了此示例以与所有示例一起使用,包括#1:
def scan(s1, s2):
# Find the longest match where s1 starts with s2
# Returns None if no matches
l = len(s1)
while 1:
if not l:
return None
elif s1[:l] == s2[:l]:
return s1[:l]
else:
l -= 1
def contains(s1, s2):
D = {} # Remove duplicates using a dict
L1 = s1.split(' ')
L2 = s2.split(' ')
# Don't add results which have already
# been processed to satisfy example #1!
DProcessed = {}
for x in L1:
yy = 0
for y in L2:
if yy in DProcessed:
yy += 1
continue
# Scan from the start to the end of the words
a = scan(x, y)
if a:
DProcessed[yy] = None
D[a] = None
break
# Scan from the end to the start of the words
a = scan(x[::-1], y[::-1])
if a:
DProcessed[yy] = None
D[a[::-1]] = None
break
yy += 1
return list(D.keys())
print contains("12 November 2010 - 1 visitor",
"6 July 2010 - 100 visitors")
print contains("Welcome, John!",
"Welcome, Peter!")
print contains("Welcome, Sam!",
"Welcome, Tom!")
哪个输出:
['1', 'visitor', '-', '2010']
['Welcome,', '!']
['Welcome,', 'm!']
例如1
>>> s1 = 'November 2010 - 1 visitor'
>>> s2 = '6 July 2010 - 100 visitors'
>>>
>>> [i for i in s1.split() if any(j for j in s2.split() if i in j)]
['2010', '-', '1', 'visitor']
>>>
对于双方
>>> s1 = "Welcome, John!"
>>> s2 = "Welcome, Peter!"
>>> [i for i in s1.replace('!',' !').split() if any(j for j in s2.replace('!',' !').split() if i in j)]
['Welcome,', '!']
>>>
注意:以上代码对于示例3不起作用,这是刚刚添加的OP
s1 = "12 November 2010 - 1 visitor"
s2 = "6 July 2010 - 100 visitors"
l1 = s1.split()
for item in l1:
if item in s2:
print item
这会在空白处分割。
在单词边界上分割的解决方案(为了捕获示例 2 中的
!
)在 Python 中不起作用,因为 re.split()
不会在零长度匹配上分割。
第三个例子,甚至使单词的任何子串都成为潜在的匹配,由于存在许多可能的变化,使事情变得更加复杂(对于
1234
,我必须检查1234
,123
, 234
、12
、23
、34
、1
、2
、3
和 4
,每增加一个数字,排列数量就会呈指数级增加。
完整的 Ruby 解决方案:
def start_similar(i, j)
front = ''
for ix in (0...([i.size, j.size].min))
if i[ix] == j[ix] then
front += i[ix].chr
else
break
end
end
return front
end
def back_similar(i, j)
back = ''
for ix in (0...([i.size, j.size].min)).to_a.reverse
dif = i.size < j.size ? j.size - i.size : i.size - j.size
ci = i[ i.size < j.size ? ix : ix + dif ]
cj = j[ i.size > j.size ? ix : ix + dif ]
if ci == cj then
back = ci.chr + back
else
break
end
end
return back
end
def scan(x, y)
a, b = x.split(' '), y.split(' ')
result = []
for i in a do
for j in b do
result << start_similar(i, j)
result << back_similar(i, j)
end
end
return result.uniq.select do |r| not r.empty? end
end
puts scan(
"12 November 2010 - 1 visitor",
"6 July 2010 - 100 visitors"
).inspect
# ["1", "2010", "0", "-", "visitor"]
puts scan(
"Welcome, John!",
"Welcome, Peter!"
).inspect
# ["Welcome,", "!"]
puts scan(
"Welcome, Sam!",
"Welcome, Tom!"
).inspect
# ["Welcome,", "m!"]