递归查找一个句子中最长的单词

问题描述：

所以我需要递归地找到最长的单词，我写了代码，但它不工作，我不知道要修复什么。递归查找一个句子中最长的单词

 public static String longestWord(String sentence) 
{ 
    int i = sentence.indexOf(" "); 

    if (i==-1){ 
     return sentence; 
    } 

    else{ 
     String first = sentence.substring(0,i); 
     String rest = sentence.substring(i+1); 

      if(first.length()>=rest.length()){ 
       return longestWord(first); 
      } 
     else{ 
      return longestWord(rest); 

     } 

    } 
}

这不是问题。请找出您感到困惑的部分，并将它们改为问题。请记住，SO不是一个为您解决作业问题的网站。 – SCdF 2012-04-12 00:24:20

欢迎来到StackOverflow。这是一个功课问题吗？如果是这样，你应该添加作业标签。您是否尝试使用调试器来遍历代码，以查看您所期望的不工作？发布一堆非工作代码并说“请修正任何错误”对于本网站来说不是一个合适的问题。请花几分钟时间阅读[常见问题]（http://stackoverflow.com/faq），以便更熟悉如何在此提问，以及哪些问题是（或不适合）提问这里。谢谢。 :) – 2012-04-12 00:26:49

它必须递归？或者是一个可接受的循环？ – kasavbere 2012-04-12 00:31:07

答

行：

if(first.length() >= rest.length())

应该象：

String res = longestWord(rest); 
if(first.length() >= res.length())

不一定。这是一个有用的优化。显然，如果第一个单词至少与字符串的其余部分一样长，则字符串的其余部分不能包含更长的单词。 – Kaz 2012-04-12 00:30:28

但是其他路径可能会丢弃原始版本中最长的单词。 – 2012-04-12 00:43:52

这是一个正确性问题，而不是优化问题。 – bdares 2012-04-12 00:44:29

答

它不工作的原因是，你忽略了longestWord(rest)的长度，而不是比较长最初的单词和句子的其余部分，你应该比较初始单词的长度和在句子其余部分找到的最长单词的长度。

String first = sentence.substring(0,i); 
String rest = longestWord(sentence.substring(i+1)); 
return first.length()>=rest.length() ? first : rest;

答

你的基本做法是明智的：你打破的输入为两个：第一个字，字符串的其余部分。但是这个逻辑有点b b。

如果第一个词是除弦的整个休息时间越长，你应该只返回first，不longestWord(first)（虽然，你这样做处理这种情况：longestWord会注意到这个词不能被拆分，就回到它这是虽然没有意义）。其次，如果不是这种情况，你就不能假设第一个单词不是最长的单词。您必须捕获返回值longestWord(rest)，然后将该字的长度与first的长度进行比较。如果这个单词更长，然后返回它。否则返回first。

递归的“分而治之”的本质是你解决了一些较小版本的问题，然后整合这些结果。不要忘记第二部分。这不是一个二进制搜索树搜索，其中数据的组织方式使得您可以递归到一半空间或另一半寻找答案。你不知道最长的单词可能在哪里。

答

这是解决问题的另一种方法：

public static String longestWord(String sentence) { 
    return longest(sentence.split("\\s+"), 0, 0); 
} 

private static String longest(String[] words, int idx, int longest) { 
    if (idx == words.length) 
     return words[longest]; 
    return longest(words, idx+1, 
     words[idx].length() > words[longest].length() ? idx : longest); 
}

首先，在longestWord()句子得到由它的空间分割，产生字的阵列。从这一点开始，方法longest()递归遍历所有通过longest参数中迄今为止发现的最长索引的单词，直到不再有单词为止。这是一个有效的答案，因为它不会在每个步骤创建子字符串。

答

package com.kota.java; 
import java.util.*; 

class LongestWord{ 
    String str = "Ram is intelligent boy"; 
    String stringArray[] = str.split("\\s"); 

    public String compare(String st1, String st2) { 
     if (st1.length() > st2.length()) { 
      return st1; 
     } else { 
      return st2; 
     } 
    } 

    LongestWord() { 
     String word = ""; 
     for (int i = 0; i < stringArray.length; i++) { 
      if (i == 0) { 
       word = stringArray[0]; 
      } 
      word = compare(word, stringArray[i]); 
     } 
     System.out.println("Longest word = " + word); 
    } 

    public static void main(String[] args) { 
     new LongestWord(); 
    } 
} 
/** 
* Out put : Longest word = intelligent 
* 
* */

递归查找一个句子中最长的单词

相关推荐