임의의 문자 열에서 단어 목록의 단어 찾기

Question

사용자가 임의의 문자를 입력 할 수있는 프로그램을 작성하고 프로그램에서 문자 및 단어 목록을 반복하여 일부 또는 전체를 포함하는 단어를 찾으려고합니다. 단어 목록의 임의의 문자. 예를 들어

: 수는 사용자로부터 입력되는 각 문자가 반복 될 질수 문자를 포함

if Input = "sasdfle" 
words found in wordlist = "sad", "fleas", "flea", etc... 

단어. 나는 여기에 anagrams을 발견하는 여러 질문을 발견했지만, 나는 위에서 언급 한 것을 할 수있는 알고리즘을 찾는 것 같다. 당신은, 예를 들어, 적절한 영어 단어 모음을 가지고 제공

Answer 1

:

내가 여기에 여기에 전체 코드를 게시하고 싶지만하지 않는 내가에 문제가하고있는 주요 부분이다

private static HashSet<String> s_Words = new HashSet<String>() { 
    "abacus", 
    //... 
    "flea", 
    "fleas", 
    //... 
    "sad", 
    "sea", 
    // ... 
    "zoom", 
}; 

당신은 키이 그 안에 정렬 된 모든 문자 ("flea" =>"aefl" 등 "sad" =>"ads")와 초기 문자열 인 더 편리 집계 사전로 변환 할 수 있습니다.

"ale", "lea" => "ael" : ["ale", "lea"] 

당신은 Linq를 통해 이러한 사전을 구현할 수 있습니다 :

private static Dictionary<String, String[]> s_Dict = s_Words 
    .Select(word => new { 
    Key = String.Concat(word.OrderBy(c => c)), 
    Value = word}) 
    .GroupBy(item => item.Key, item => item.Value) 
    .ToDictionary(chunk => chunk.Key, chunk => chunk.ToArray()); 

두 개 이상의 단어가 같은 키를 가지고 있다면, 그들은 이 모음으로을 결합, 말, 배열해야한다 그런 다음 문자열을

String Input = "sasdfle" 

당신이 할 필요가있다 종류 에 부여 93,692,858,을하고 각 문자를 포함하고 excuding 단지 256 (2 ** (length + 1) == 256) 조합 확인 :

string source = String.Concat(Input.OrderBy(c => c)); 

// all combinations of the set with empty one excluded, see 
// http://stackoverflow.com/questions/30081908/c-sharp-linq-combinatorics-all-combinations-of-a-set-without-the-empty-set/30082360#30082360 
var result = Enumerable 
    .Range(1, (1 << source.Length) - 1) 
    .Select(index => string.Concat(source.Where((item, idx) => ((1 << idx) & index) != 0))) 
    .SelectMany(key => { 
    String[] words; 

    if (s_Dict.TryGetValue(key, out words)) 
     return words; 
    else 
     return new String[0]; }) 
    .Distinct() // some words can be built in many ways 
    .OrderBy(word => word); 
//.ToArray(); // if you want to represent words as array 

테스트

Console.Write(String.Join(Environment.NewLine, result)); 

가 반환됩니다

flea 
fleas 
sad 
sea