두 개의 문자열 S와 T가 있다고 가정하고 사전순으로 S보다 크고 T보다 작은 동일한 길이의 문자열을 확인해야 합니다. 그런 문자열을 사용할 수 없으면 -1을 반환해야 합니다. S =S1S2… Sn은 사전식으로 T =T1T2… Tn보다 작다고 합니다. 단 i가 존재하면 S1=T1, S2=T2, … 시
따라서 입력이 S ="bbb" 및 T ="ddd"와 같으면 출력은 "bbc"가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=문자열 크기
- n - 1에서 0 사이의 i에 대해 1 감소, do
- 문자열[i]가 'z'와 같지 않으면
- k :=(문자열[i])의 ASCII
- string[i] :=ASCII 문자(k + 1)
- 문자열을 결합하고 반환
- 문자열[i] :='아'
- 문자열[i]가 'z'와 같지 않으면
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def find_next(string): n = len(string) for i in range(n - 1, -1, -1): if string[i] != 'z': k = ord(string[i]) string[i] = chr(k + 1) return ''.join(string) string[i] = 'a' S = "bbb" T = "ddd" S = list(S) res = find_next(S) if res != T: print(res) else: print(-1)
입력
"bbb", "ddd"
출력
bbc