2011-07-20 15 views
0

2つのCharリストをチェックするjavaで再帰的メソッドを作成する必要があります。 2番目のリストに最初のリスト内のすべての文字が少なくとも1回同じ順序で含まれている場合はtrueを返し、そうでない場合はfalseを返す必要があります。 例:Javaでリンクされたリスト - 2つのリストを比較する

リスト1: "abbcd"(ノード内のすべての文字)、リスト2: "abbcccddd"(ノード内のすべての文字)これはtrueを返します。

例2: "abbcd"、リスト2: "abcd"これはfalseを返します。

私にはいくつかのアイデアがありますが、明確な解決策には達しません。 アイデアは誰ですか?

+3

あなたのアイデアは何ですか? – Grammin

+1

宿題の場合は、そのまま宿題にしてください。 – home

+0

ところで:例2はなぜ 'false'を返すべきですか? – home

答えて

1

通常のノード構造でデータ要素と次のノードへの参照を使用すると仮定します。次のように一つの機能を定義することができる:

  • (nullの、干し草の山)を含有する真=(すべての文字列が空の文字列が含まれているため)

  • は(パターン、NULL)=偽(空ので含ま文字列が)

  • を任意のパターンが含まれていない(パターン、干し草の山)が含ま= pattern.data = haystack.data (我々が試合を見つけて、次の項目に進む場合(pattern.next、haystack.next)が含まれてい両方のリストで)

  • は(パターン、干し草の山)が含ま=(pattern.next、haystack.next)他に含まれています(私たちは一致を発見したと干し草の山の次の文字でそれを試してみてください)

0

要件も順に問題を単純化する。

は、両方のリストが若干異なる進めるルールと同時ににわたり繰り返されていることを考えてみましょう:

  1. リストは、次のノードへの高度な「発見する」である場合には?
  2. "見つかる"リストを含むリストが次のノードに進むのはいつですか?
  3. "見つかる"リストが他のリストに含まれていないのはいつですか?
  4. どの時点で一致が判定されますか?
  5. どのように各リストを反復処理できますか?どのように再帰的に行うことができますか?

ハッピーコーディング。

関連する問題