예를 들어, 문자열이 있습니다.
s = "Hello, stack exchange. Let's solve my query"
그리고 3 개의 부분 문자열이 있다고합시다.
s1 = "solve"
s2 = "stack"
s3 = "Not present"
s에서 먼저 오는 부분 문자열을 결정하는 지름길이 있습니까?
나는 substrs의 인덱스를 찾을 수있는 함수를 작성할 수 있고, 아마도 substr-index 쌍을 사전에 저장 한 다음 음수가 아닌 모든 인덱스를 비교할 수 있지만 이것을 수행하는 더 짧은 방법이나 파이썬적인 방법이 있습니까?
생성기를 사용하여 모든 위치 min()
를 찾고 가장 왼쪽의 위치를 찾을 수 있습니다 .
positions = (s.find(sub), sub) for sub in (s1, s2, s3))
leftmost = min((pos, sub) for pos, sub in positions if pos > -1)[1]
이는 s.find()
각 하위 문자열에 대해 한 번만 실행되며 존재하지 않는 하위 문자열을 필터링합니다. 일치하는 부분 문자열이 전혀 없으면 예외 min()
가 ValueError
발생합니다. 당신은 그것을 잡을 수 있습니다.
이것은 문자열을 3 번 스캔합니다. 테스트 된 부분 문자열의 수가 충분히 크면 대신 trie 구조 를 만들고 인덱스를 반복 s
하고 해당 위치의 문자가 trie에 있는지 테스트합니다.
def make_trie(*words):
root = {}
for word in words:
current = root
for letter in word:
current = current.setdefault(letter, {})
# insert sentinel at the end
current[None] = None
return root
def find_first(s, trie):
for i in range(len(s)):
pos, current, found = i, trie, []
while pos < len(s) and s[pos] in current:
found.append(s[pos])
current = current[s[pos]]
if None in current: # whole substring detected
return ''.join(found)
pos += 1
leftmost = find_first(s, make_trie(s1, s2, s3))
트라이는 여러 문자열에 재사용 할 수 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다