단어 뒤범벅 (즉, ofbaor)이 주어지면 실제 단어 (즉, foobar)를 만들기 위해 글자를 해독하는 방법은 무엇이겠습니까? 이것에 대해 몇 가지 접근법이 있습니다. .NET에서 어떻게 구현하는지 알고있을 것 같지만 다른 솔루션이 어떻게 보이는지 궁금합니다 (내 솔루션이 최적인지 아닌지 항상 알 수 있습니다).단어 뒤죽박죽 알고리즘
이것은 숙제가 아니거나 그저 종이의 로컬 만화 섹션 (예, good ol 'fashioned newsprint)에서 단어가 뒤섞여있는 것을 보았습니다. 내 엔지니어가 생각하기 시작했습니다.
편집 : 가능한 경우 의사 코드 또는 실제 코드를 게시하십시오. 이런 예를보고 언어 지식을 확장하고 확장하는 것은 항상 좋은 일입니다.
각 단어의 문자가 정렬 된 순서로 키워지는 사전이 있습니다. 그런 다음 문자를 정렬하여 뒤집습니다. 사전에있는 모든 단어를 정렬 된 문자열로 찾습니다.
그래서 다음과 같이, 예를 들어, 단어 '곰'과 '맨'으로 사전에있을 것입니다 :
key word
----- ------
aber bear
aber bare
을 그리고 당신이 뒤범벅, 'earb'을 제공하는 경우, 당신은 좋겠 편지를 'aber'로 정렬하고 사전에서 가능한 두 단어를 찾을 수 있습니다.
문자열의 모든 순열을 만들고 사전에서 찾아 봅니다.
단어를 시작하는 짧은 문자열을 찾은 다음 해당 문자열로 시작하는 적절한 길이의 단어가 사전에없는 경우 해당 문자로 시작하는 순열을 추가로 고려하지 않고 최적화 할 수 있습니다.
문자열의 길이에 따라 WhirlWind의 접근 방식은 더 빨라질 수 있지만 O (n) 복잡도가있는 대체 방법은 문자열의 모든 순열을 작성하여 찾는 것이 아니라 사전의 모든 단어를 살펴보고 입력 문자열에서 각 단어를 만들 수 있는지 확인하십시오. 미리 사전에있는 단어의 수를 알고
정말 스마트 알고리즘은 다음과 같이 뭔가를 할 수 :
sort letters in jumbled string
if factorial(length of jumbled string) > count of words in dictionary:
for each word in dictionary:
sort letters in dictionary word
if sorted letters in dictionary word == sorted letters in jumbled string:
append original dictionary word to acceptable word list
else:
create permutation list of jumbled letters
for each permutation of letters:
search in dictionary for permutation
if permutation in dictionary:
add word to acceptable word list