대체 후 하위 문자열 일치
s
및 sub
두 개의 문자열이 제공됩니다. 또한 2D 문자 배열mappings
이 제공됩니다. 여기서 mappings[i] = [oldi, newi]
는 oldi
의 sub
문자를 newi
로 바꿀 수 있음을 나타냅니다. sub
의 각 문자는 두 번 이상 바꿀 수 없습니다.true
에 따라 0개 이상의 문자를 교체하여 sub
의 하위 문자열을 s
만들 수 있는 경우 mappings
를 반환합니다. 그렇지 않으면 false
를 반환합니다.하위 문자열은 문자열 내에서 비어 있지 않은 연속적인 문자 시퀀스입니다.
예 1:
입력: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
출력: 참
설명: sub의 첫 번째 'e'를 '3'으로 바꾸고 sub의 't'를 '7'로 바꿉니다.
이제 sub = "l3e7"은 s의 하위 문자열이므로 true를 반환합니다.
예 2:
입력: s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
출력: 거짓
설명: 문자열 "f00l"은 s의 하위 문자열이 아니므로 대체할 수 없습니다.
'0'을 'o'로 바꿀 수 없습니다.
예 3:
입력: s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d ","b"],["p","b"]]
출력: 참
설명: sub의 첫 번째와 두 번째 'e'를 '3'으로 바꾸고 sub의 'd'를 'b'로 바꿉니다.
이제 sub = "l33tb"는 s의 하위 문자열이므로 true를 반환합니다.
제약:
1 <= sub.length <= s.length <= 5000
0 <= mappings.length <= 1000
mappings[i].length == 2
oldi != newi
s
및 sub
는 영문 대문자와 소문자 및 숫자로 구성됩니다. oldi
및 newi
는 영문 대문자 또는 소문자 또는 숫자입니다. 해결책:
from collections import defaultdict
import re
class Solution:
def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
reachable = defaultdict(set)
for a, b in mappings:
reachable[a].add(b)
for c in sub:
reachable[c].add(c)
regex = ""
for c in sub:
if len(reachable[c]) > 1:
regex += "("
regex += "|".join(reachable[c])
regex += ")"
else:
regex += c
return re.compile(regex).search(s)
Reference
이 문제에 관하여(대체 후 하위 문자열 일치), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/theabbie/match-substring-after-replacement-3f6a텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)