0

目前正在摆弄我正在做的一个小项目,这是一个倒计时类型的游戏(电视节目)。目前,该程序允许用户选择最多 9 个字母的元音或辅音,然后要求他们使用这 9 个字母输入他们能想到的最长单词。

我有一个大文本文件充当字典,我使用用户输入的字符串搜索它以尝试匹配结果以检查他们输入的单词是否是有效单词。我的问题是,我想在字典中搜索由九个字母组成的最长单词,但我似乎无法找到实现它的方法。

到目前为止,我已经尝试将每个单词放入一个数组并搜索每个元素以检查它是否包含字母,但如果可以从 9 个字母中组成的最长单词是 8 个字母的单词,这不会涵盖我。有任何想法吗?目前我有这个(这是在表单上的提交按钮下,很抱歉没有提供代码或提到它是一个 Windows 表单应用程序):

StreamReader textFile = new StreamReader("C:/Eclipse/Personal Projects/Local_Projects/Projects/CountDown/WindowsFormsApplication1/wordlist.txt");
int counter1 = 0;
String letterlist = (txtLetter1.Text + txtLetter2.Text + txtLetter3.Text + txtLetter4.Text + txtLetter5.Text + txtLetter6.Text + txtLetter7.Text + txtLetter8.Text + txtLetter9.Text); // stores the letters into a string
char[] letters = letterlist.ToCharArray(); // reads the letters into a char array
string[] line = File.ReadAllLines("C:/Eclipse/Personal Projects/Local_Projects/Projects/CountDown/WindowsFormsApplication1/wordlist.txt"); // reads every line in the word file into a string array (there is a new word on everyline, and theres 144k words, i assume this will be a big performance hit but i've never done anything like this before so im not sure ?)

line.Any(x => line.Contains(x)); // just playing with linq, i've no idea what im doing though as i've never used before
for (int i = 0; i < line.Length; i++)// a loop that loops for every word in the  string array
//  if (line.Contains(letters)) //checks if a word contains the letters in the char array(this is where it gets hazy if i went this way, i'd planned on only using words witha  letter length > 4, adding any words found to another text file and either finding the longest word then in this text file or keeping a running longest word i.e.  while looping i find a word with 7 letters, this is now the longest word, i then go to the next word and it has 8 of our letters, i now set the longest word to this)

counter1++;
if (counter1 > 4)

txtLongest.Text += line + Environment.NewLine;

迈克的代码:

using System;

使用 System.Collections.Generic;使用 System.Linq;

课堂节目

static void Main(string[] args) {
    var letters = args[0];

    var wordList = new List<string> { "abcbca", "bca", "def" }; // dictionary

    var results = from string word in wordList // makes every word in dictionary into a seperate string
                  where IsValidAnswer(word, letters) // calls isvalid method
                  orderby word.Length descending // sorts the word with most letters to top
                  select word; // selects that word

    foreach (var result in results) {
        Console.WriteLine(result);    //  outputs the word
    }
}

private static bool IsValidAnswer(string word, string letters) {
    foreach (var letter in word) {
        if (letters.IndexOf(letter) == -1) { // checks if theres letters in the word
            return false;
        }

        letters = letters.Remove(letters.IndexOf(letter), 1);
    }

    return true;
}

}

4

6 回答 6

1

这是我在几分钟内敲定的答案,应该可以满足您的要求。正如其他人所说,这个问题很复杂,所以算法会很慢。LINQ 查询评估字典中的每个字符串,检查提供的字母是否可用于生成所述单词。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        var letters = args[0];

        var wordList = new List<string> { "abcbca", "bca", "def" };

        var results = from string word in wordList
                      where IsValidAnswer(word, letters)
                      orderby word.Length descending
                      select word;

        foreach (var result in results) {
            Console.WriteLine(result);    
        }
    }

    private static bool IsValidAnswer(string word, string letters) {
        foreach (var letter in word) {
            if (letters.IndexOf(letter) == -1) {
                return false;
            }

            letters = letters.Remove(letters.IndexOf(letter), 1);
        }

        return true;
    }
}
于 2013-02-21T17:14:38.620 回答
0

第 1 步:构建每个单词按字母排序的 trie 结构。

示例:EACH 排序为 ACEH 在 trie 中存储为 A->C->E->H->(EACH, ACHE, ..) (ACHE 是 EACH 的变位词)。

步骤2:对输入的字母进行排序,在trie中找到与该组字母对应的最长单词。

于 2013-02-22T02:14:56.690 回答
0

我对此有了更多的想法。我认为有效地做到这一点的方法是通过预处理字典,按字母顺序对每个单词中的字母进行排序,并按字母顺序对列表中的单词进行排序(您可能必须使用某种多映射结构来存储原始单词和排序后的词)。

完成此操作后,您可以更有效地找到可以从字母池中生成的单词。如果其他人没有击败我,我稍后会回来充实执行此操作的算法。

于 2013-02-22T00:08:43.317 回答
0

那么你在哪里卡住了?从缓慢的蛮力方法开始,只需找到包含所有字符的所有单词。然后按长度排序单词以获得最长的单词。如果您不想返回一个比要查找的字符数短的单词(我猜只有在存在重复字符时才会出现问题???),然后添加一个测试并消除这种情况。

于 2013-02-21T16:55:40.353 回答
-1

您是否尝试过实施这样的事情?很高兴看到您尝试过的代码。

string[] strArray = {"ABCDEFG", "HIJKLMNOP"};
string findThisString = "JKL";
int strNumber;
int strIndex = 0;
for (strNumber = 0; strNumber < strArray.Length; strNumber++)
{
    strIndex = strArray[strNumber].IndexOf(findThisString);
    if (strIndex >= 0)
        break;
}
System.Console.WriteLine("String number: {0}\nString index: {1}",
    strNumber, strIndex);
于 2013-02-21T16:55:25.717 回答
-1

这必须完成工作:

private static void Main()
{
    char[] picked_char = {'r', 'a', 'j'};
    string[] dictionary = new[] {"rajan", "rajm", "rajnujaman", "rahim", "ranjan"};
    var words = dictionary.Where(word => picked_char.All(word.Contains)).OrderByDescending(word => word.Length);


    foreach (string needed_words in words)
    {
        Console.WriteLine(needed_words);
    }
}

输出 :


rajnujaman
ranjan
rajan
rajm

于 2013-02-21T17:10:12.383 回答