2

假设我有一系列不完全限定的路径，它们缺少某些部分，但保证具有两个属性：

  1. 不完全和完全限定路径的最后部分将完全相等，并且
  2. 不完全限定路径的每个部分的顺序将与完全限定路径的部分的实际顺序相匹配。

例如，

p1 = '/foo/baz/myfile.txt'
p2 = '/bar/foo/myfile.txt'
actual = '/foo/bar/baz/myfile.txt'

在这种情况下，p1会匹配，但p2不会匹配，因为在实际路径中，bar会出现在foo. 很简单：[actual.split('/').index(part) for part in p1.split('/')]将是一个有序列表，但相同的理解但 forp2不会。

但是如果路径中有重复会发生什么？

p1 = '/foo/bar/bar/myfile.txt'
p2 = '/bar/bar/baz/myfile.txt'
actual = '/foo/bar/baz/bar/myfile.txt'

我怎样才能确定p1匹配，但不匹配p2（因为，虽然baz发生在第一个之后bar，但它不会在第二个之后发生？

4

2 回答 2

1

方法1：使用list.index：

def match(strs, actual):
    seen = {}
    act = actual.split('/')
    for x in strs.split('/'):
        if x in seen:
            #if the item was already seen, so start search 
            #after the previous matched index
            ind = act.index(x, seen[x]+1)
            yield ind
            seen[x] = ind
        else:
            ind = act.index(x)
            yield ind
            seen[x] = ind
...             
>>> p1 = '/foo/baz/myfile.txt'
>>> p2 = '/bar/foo/myfile.txt'
>>> actual = '/foo/bar/baz/myfile.txt'
>>> list(match(p1, actual))     #ordered list, so matched
[0, 1, 3, 4]
>>> list(match(p2, actual))     #unordered list, not matched
[0, 2, 1, 4]

>>> p1 = '/foo/bar/bar/myfile.txt'
>>> p2 = '/bar/bar/baz/myfile.txt'
>>> actual = '/foo/bar/baz/bar/myfile.txt'
>>> list(match(p1, actual))     #ordered list, so matched
[0, 1, 2, 4, 5]
>>> list(match(p2, actual))     #unordered list, not matched
[0, 2, 4, 3, 5]

方法2：使用defaultdictand deque：

from collections import defaultdict, deque
def match(strs, actual):
    indexes_act = defaultdict(deque)
    for i, k in enumerate(actual.split('/')):
        indexes_act[k].append(i)
    prev = float('-inf')
    for item in strs.split('/'):
        ind = indexes_act[item][0]
        indexes_act[item].popleft()
        if ind > prev:
            yield ind
        else:
            raise ValueError("Invalid string")
        prev = ind

演示：

>>> p1 = '/foo/baz/myfile.txt'
>>> p2 = '/bar/foo/myfile.txt'
>>> actual = '/foo/bar/baz/myfile.txt'
>>> list(match(p1, actual))
[0, 1, 3, 4]
>>> list(match(p2, actual))
    ...
    raise ValueError("Invalid string")
ValueError: Invalid string

>>> p1 = '/foo/bar/bar/myfile.txt'
>>> p2 = '/bar/bar/baz/myfile.txt'
>>> actual = '/foo/bar/baz/bar/myfile.txt'
>>> list(match(p1, actual))
[0, 1, 2, 4, 5]
>>> list(match(p2, actual))
    ...
    raise ValueError("Invalid string")
ValueError: Invalid string
于 2013-09-24T17:41:36.960 回答
1 
def match(path, actual):
    path = path.strip('/').split('/')
    actual = iter(actual.strip('/').split('/'))
    for pathitem in path:
        for item in actual:
            if pathitem == item:
                break
        else:
            # The for-loop never breaked, so pathitem was never found
            return False
    return True

q1 = '/foo/baz/myfile.txt'
q2 = '/bar/foo/myfile.txt'
p1 = '/foo/bar/bar/myfile.txt'
p2 = '/bar/bar/baz/myfile.txt'
actual = '/foo/bar/baz/bar/myfile.txt'

print(match(q1, actual))
# True

print(match(q2, actual))
# False

print(match(p1, actual))
# True

print(match(p2, actual))
# False
于 2013-09-24T17:45:25.773 回答