나는 단어 게임을 쓰고 있습니다. 단어를 확인하기 위해 사전 개체에 액세스 할 수 있습니다. 단어와 추가 문자 집합을 포함하는 가능한 모든 단어를 찾아야합니다. 예를 들어 은 단어가 "MEN"이고 추가 문자 집합이 "WALOHTD"라고 말합니다. 나는 같은 단어를 찾을 수있는 방법이 필요합니다 .... 1.MEND 2.WOMEN 3.MENTAL 4. etc .... 기본적으로 우리는 "MEN"을 포함하는 가능한 모든 단어를 찾고 있습니다. 특정 추가 문자.사전이 있으면 특정 문자 집합과 문자열이 포함 된 가능한 모든 단어를 찾는 최적의 방법은 무엇입니까
전체 사전을 통해 하위 단어가 포함 된 첫 번째 단어로 반복 한 다음 특정 문자 존재 여부를 확인하지만 최적이 아닌 코드를 작성할 수 있습니다. 1 초 이상 걸립니다. 최적의 솔루션을 향한 도움은 대단히 감사하겠습니다. _rey
문제는 정규 언어와 데이터 구조를 검색하는 문제입니다.
첫 번째 측면 만 고려하면 정규 표현식을 사용하는 경향이 있습니다. 당신은 우리가 "추가 문자"를 반복 할 수 있는지 말하지 않습니다. 가능한 경우 [WALOTHD]*MEN[WALOTHD]*을 쉽게 처리 할 수 있으며 쉽게 적용 할 수 있습니다.
우리가 반복 할 수 없다면, [WALOTHD]{0,7}MEN[WALOTHD]{0,7}으로 시작하여 규칙을 어기는 모든 것을 필터링 할 수 있습니다 ("할당"은 해당 표현식과 일치하지만 L과 T를 반복합니다).
또는 더 복잡한 표현식을 사용했을 때 얻은 이득이 그것이 무엇인지 알아내는 데 드는 비용보다 비싸지는 않을지라도 훨씬 더 복잡한 정규 표현식을 만들려고 할 수 있습니다.
사전 검색의 반대편에서 볼 때 DAWG은 매우 공간 효율적이어서 부분 문자열을 포함하는 일치 항목을 상대적으로 효율적으로 찾을 수 있습니다. 우리가 접두사와 접미어를 걱정할 정도의 순열을 가지고 있기 때문에이 퍼즐과 완전히 일치하지는 않습니다. 테스트가 없다면, 우리는 "추가"에서 반복 할 수 없다면 합리적으로 좋을 것이라고 추측 할 수 있습니다. 그러나 이것은 단지 추측 일뿐입니다. GADDAG는 가치가 있을지도 모르지만 DAWG보다 크지 만 이러한 검색에는 더 빠를 것입니다 (GADDAG는 스크래블 해결에 사용됩니다.이 문제는 여기에있는 것과 거의 같은 문제입니다).
빠른 응답을 보내 주셔서 감사합니다. 언급 한 것처럼 일반 정규 표현식을 생각하고 있었지만 문제는 루프에서 수천 개의 항목을 나열해야한다는 것이고 시간 관점에서 볼 때 매우 비싸게되고 있습니다. – user1626251
DAWGs와 GADDAGs, 특히 후자에 대해 읽어 보는 것이 좋습니다. DAWGs 만 사용했으나 GADDAGs는 스크랩 풀기에 매우 능숙합니다. 이것은 여러분이 가지고있는 것에 가깝습니다. –
정규식으로 해결할 수 있습니다 :''[WALOTHD] * MEN [WALOTHD] * "',이 특정 예제의 경우 문제가 시간이 될 것입니다. 어떤 데이터 구조를 사용하고 있습니까? – rendon