부분 문자열을 일치시켜 문자열 배열의 문자열 완성

Question

이것은 한 번 묻는 질문의 작은 부분입니다.

입력리스트 [] = I는 [] = {ABCD, xyzw, qwer, ABCDE}

그리고 내 입력된다

STR리스트 같은 문자열 변수 배열을 {AB, ABC, Q, Z, X}

출력해야 할 [] = {ABCD, ABCD, qwer, -} xyzw

각 입력 문자열은 목록의 첫 문자부터 동일한 문자 ()와 일치해야합니다. 첫 번째 사용 가능한 문자열을 대답으로 제공해야합니다.

의 I이었다 생각할 수있는 접근 워킹 -

1. 브 루트 포스 : 입력의 시간 복잡도 O ((목록에있는 문자열)의 수 * (입력 문자열의 평균 길이) * (숫자 문자열))

2. 해싱 : 역시 같은 시간이 걸립니다.

더 좋은 방법이 있나요?

Answer 1

귀하의 목록 []이 고쳐 지거나 (많이 변경되지 않는 경우), 트릭이 트릭을 수행합니다. 삽입하는 동안 "첫 번째 일치"를 식별하기 위해 약간의 논리를 수행해야합니다. 따라서 "abcd"가 첫 번째 항목 인 경우 "abcde"를 삽입하면 안됩니다 (또는 "abcd"를 무시할 수 없으면 무효화하십시오. 약간의 회계와 부기를해야한다.)

세부 정보 : http://en.wikipedia.org/wiki/Trie