0

假设我有一个带有字符串的 txt 文件，并且我有开始词和结束词。我需要找到起始词和结束词之间的所有单词，它们相差一个字符。如何查找一个字符不同的字符串？我是否需要将从文件中读取的字符串分解为字符并与我的开始和结束字符串进行比较

4

3 回答 3

0

在此处输入图像描述

Theres 需要一些递归函数来找到最短路径。

于 2013-10-18T21:41:50.440 回答
0

我需要找到起始词和结束词之间的所有单词，它们相差一个字符；因此，从给出的示例中，我的结果将是：AAAA、ABZZ 和 AAZZ。

这个任务看起来很简单，但我对你的例子有点困惑......我相信你会得到下一个列表：

AAAA ABAA ABZA ABZZ AAZZ

这是示例：

 private int Differs(string Word1, string Word2) //calculates how much letters differs in 2 words
        {
         //Here should be some checks to prevent index out of range error during cycle
         int result=0;
         for(int i=0;i<Word1.Length;i++) 
         if(Word1[i]!=Word2[i]) result++;
         return result;
        }

 public List<string> ArrangeWords(string StartWord, string EndWord, List<string> Words)
        {
            List<string> ResultWords = new List<string>();
            string CurrentWord = StartWord;
            Words.Remove(StartWord); //removing start and end words from list
            Words.Remove(EndWord);
            ResultWords.Add(StartWord);
            while (Words.Count > 0) //Searching next words and moving them to result list until Source List becomes empty
            {
                List<string> neubourwords = Words.FindAll(x => Differs(CurrentWord, x) == 1);
                if (neubourwords.Count > 0)
                {
                    CurrentWord = neubourwords[0];
                    ResultWords.Add(CurrentWord);
                    Words.Remove(CurrentWord);
                }
                else return null; //wrong source sequence!
            }
            ResultWords.Add(EndWord);
            return ResultWords;
        }


 private void Button_Click_2(object sender, RoutedEventArgs e)
        {
            string StartWord = "AAAA";
            string EndWord = "AAZZ";
            List<string> Words = new List<string>() { "ABAA", "AAAA", "ABZA", "ABZZ", "AAZZ" }; //List, loaded from file
            List<string> ArrangedWords=ArrangeWords(StartWord,EndWord,Words);
}

在单词复杂性增加的情况下，该任务将非常类似于使用图形的 DNA 测序算法 ( http://veda.cs.uiuc.edu/courses/fa09/cs466/lectures/Lecture9.pdf )。

于 2013-10-18T19:30:46.700 回答
0

这称为字符串之间的距离。看看这个：（Levenshtein距离）

http://www.dotnetperls.com/levenshtein http://en.wikipedia.org/wiki/Levenshtein_distance

于 2013-10-18T21:47:07.073 回答