再帰的な長い言葉プログラミング
-
28-10-2019 - |
質問
私はついに自分が欲しいもののようにそれをやった。助けてくれてありがとう、そして私はそれが宿題ではなかったことを強調したいと思います。
public static void main(String[] args) {
String input = "Java is a programming language";
StringTokenizer st = new StringTokenizer(input);
System.out.print(longestWord(input));
}
public static String longestWord(StringTokenizer st) {
if (!st.hasMoreTokens()) {
return "";
} else {
String token = st.nextToken();
String longestInTheRest = longestWord(st);
if (token.length() > longestInTheRest.length()) {
return token;
} else {
return longestInTheRest;
}
解決
より機能的なスタイルで書かれた別のソリューション - 各呼び出しで新しい文字列を再帰的な方法に割り当てていないことに注意してください( split
最初の操作は、新しい文字列を割り当てます)。また、最初に元の問題を配列上の再帰に変換するというロバートの提案を受け取りました。それは物事をより簡単にします。
public static String longestWord(String s) {
return longestWord(s.split("\\s+"), 0, 0);
}
public static String longestWord(String[] words, int currentIdx, int longestIdx) {
if (currentIdx == words.length)
return words[longestIdx];
return longestWord(words, currentIdx + 1,
words[currentIdx].length() > words[longestIdx].length() ? currentIdx : longestIdx);
}
上記の解決策のトリックは、私の再帰が進行することです インデックス 文字列アレイのものであり、文字列自体の上ではありません。それが、各コールで新しい文字列の作成を避けない理由です。いいえ substring
, copyOfRange
, arraycopy
, new String()
または同様の操作が必要であり、よりエレガントなソリューションが得られます。
編集:
理解しやすくするために、上記のコードを少し簡素化しました。に関して split
方法それは標準の文字列操作です、 ドキュメンテーション.
public static String longestWord(String s) {
return longestWord(s.split(" "), 0, 0);
}
public static String longestWord(String[] words, int currentIdx, int longestIdx) {
if (currentIdx == words.length)
return words[longestIdx];
int idx; // temporarily stores the index of the current longest word
if (words[currentIdx].length() > words[longestIdx].length())
idx = currentIdx;
else
idx = longestIdx;
return longestWord(words, currentIdx + 1, idx);
}
他のヒント
以下は正しくありません:
else if (token.length() > result.length()) {
上記のステートメントが実行されると、 result
いつも " "
.
何の関数 したほうがいい (1)の長さの大きい方を返します。 token
; (2)再帰コールによって返された単語の長さ。
また、2つかどうかを考えるかもしれません s.substring()
通話は、あなたが望むことを正確に行うか、問題があるかどうかを実行します。印刷 token
と rest
(またはデバッガーでそれらを調べる)が役立つ場合があります。
これは宿題のように見えるので、ここでやめます。
現在の単語を結果と比較していますが、結果は常にに設定されているローカル変数です " "
(ところで、これは空の文字列ではなく、空白を含む文字列です)。
現在の結果をメソッドの引数として渡し、結果として空の文字列から始めてください。
トークンをトリミングしないため、バグもあります。したがって、主要な空白を単語の一部と見なします。
仕事に再帰するためには、現在の状態である現在の最も長い単語を渡す必要があります。
宿題のように見えるなら、答えは含まれていません。そうでないかどうか教えてください。
result = token;
return longestWord(rest);
これは間違った部分です。結果はトークンを保存しますが、メソッドを終了し、もう一度入力して結果を「」に設定します。メソッドの署名に別のパラメーター文字列をcurentlongestに追加して、紛失しないようにします。
スペースが残っているかどうかをテストする必要があります。
何かのようなもの
int index = s.indexOf(' ');
if (index < 0) return s;
私はこれを解決するために少し異なるアプローチを取ります:
まず、文字列を再帰的な方法に適した配列に変換します。
public static String longestWord(String string) {
return longestWord(string.split(" "), "");
}
その後、再帰的な方法について考えることができます。小さい配列を再帰的に通過すると、最終的に空の配列を渡すことがわかります。つまり、すべての要素を列挙しているので、パラメーターとして渡された最長の要素を返してください。再帰的なケースでは、(現在の)アレイの最初の要素が現在の最も長いものよりも長いかどうかを確認し、2つの長さで再帰的に通過することを再帰的に呼び出します。
private static String longestWord(String[] strings, String currentLongest) {
if (strings == null || strings.length == 0) {
return currentLongest;
}
String[] newStrings = Arrays.copyOfRange(strings, 1, strings.length);
String longest = strings[0].length() < currentLongest.length() ? currentLongest : strings[0];
return longestWord(newStrings, longest);
}
注:これは、インデックスをコピーするのではなく、アレイにインデックスに使用することで達成することもできます。ただし、実際には、これは最適化が行き過ぎています。読みにくいことが難しくなり、誰にでも利益をもたらす可能性は低いです。