"[", "|" 및 "]"와 같은 다른 문자와 소문자 알파벳 문자열이 있다고 가정합니다. 여기서 "[a|b|c]"는 "a", "b" 또는 "c"가 가능성으로 선택될 수 있음을 나타냅니다. s가 나타낼 수 있는 모든 가능한 값을 포함하는 문자열 목록을 찾아야 합니다. 여기서 "[]"는 중첩될 수 없으며 선택 항목의 수에 제한이 없습니다.
따라서 입력이 s ="[d|t|l]im[e|s]"와 같으면 출력은 ['dime', 'dims', 'lime', 'lims', 'time'이 됩니다. , '팀']
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- s가 비어 있으면
- 빈 문자열이 있는 목록 반환
- n :=s의 크기
- seq :=새 목록, res :=새 목록
- helper() 함수를 정의합니다. 이것은 pos
- 이 걸릴 것입니다
- pos가 n과 같으면
- seq에 있는 각 요소를 결합하고 res에 삽입
- 그렇지 않으면
- s[인덱스 위치에서 끝까지]의 하위 문자열에 "["이면
- start :=pos + s의 하위 문자열에 있는 "["의 인덱스[인덱스 위치에서 끝까지]
- end :=pos + s의 하위 문자열에 있는 "]"의 인덱스[인덱스 pos에서 끝까지]
- "|"로 분할된 시작부터 끝까지 s의 하위 문자열에 있는 각 옵션에 대해 do
- seq 끝에 s[인덱스 위치부터 시작 - 1] 삽입
- seq 끝에 옵션 삽입
- 도우미(end + 1)
- seq에서 마지막 두 요소 삭제
- s[인덱스 위치에서 끝까지]의 하위 문자열에 "["이면
- 그렇지 않으면
- seq 끝에 s[인덱스 위치에서 끝까지] 삽입
- 도우미(n)
- seq에서 마지막 요소 삭제
- pos가 n과 같으면
- 기본 방법에서 다음을 수행합니다.
- 도우미(0)
- 정렬된 순서로 결과 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
class Solution:
def solve(self, s):
if not s:
return [""]
n = len(s)
def helper(pos):
if pos == n:
res.append("".join(seq))
else:
if "[" in s[pos:]:
start = pos + s[pos:].index("[")
end = pos + s[pos:].index("]")
for option in s[start + 1 : end].split("|"):
seq.append(s[pos:start])
seq.append(option)
helper(end + 1)
seq.pop()
seq.pop()
else:
seq.append(s[pos:])
helper(n)
seq.pop()
seq = []
res = []
helper(0)
return sorted(res)
ob = Solution()
s = "[d|t|l]im[e|s]"
print(ob.solve(s)) 입력
"[d|t|l]im[e|s]"
출력
['dime', 'dims', 'lime', 'lims', 'time', 'tims']