1

この特定のインタビューの質問は私を困惑させました：

Given two Strings S1 and S2. Find the longest Substring which is a Prefix of S1 and suffix of S2.

Google を通じて、次のソリューションに出くわしましたが、それが何をしているのかよくわかりませんでした。

public String findLongestSubstring(String s1, String s2) {
        List<Integer> occurs = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(s2.length()-1)) {
                occurs.add(i);
            }
        }

        Collections.reverse(occurs);

        for(int index : occurs) {
            boolean equals = true;
            for(int i = index; i >= 0; i--) {
                if (s1.charAt(index-i) != s2.charAt(s2.length() - i - 1)) {
                    equals = false;
                    break;
                }
            }
            if(equals) {
                return s1.substring(0,index+1);
            }
        }

        return null;
    }

私の質問:

  1. このソリューションはどのように機能しますか?
    • そして、このソリューションを発見するにはどうすればよいでしょうか?
  2. より直感的で簡単なソリューションはありますか?
4

4 に答える 4

4

質問のパート 2

これは短い変種です：

public String findLongestPrefixSuffix(String s1, String s2) {

   for( int i = Math.min(s1.length(), s2.length()); ; i--) {
      if(s2.endsWith(s1.substring(0, i))) {
         return s1.substring(0, i);
      }
   }    
}

Math.minそれ以上比較する必要がなく、比較できないため、最短の文字列の長さを見つけるために使用しています。

someString.substring(x,y)xcharacter から始まり、 characterで停止するsomeString を読み取るときに取得する文字列を返しますy。可能な最大の部分文字列 (s1またはs2) から可能な限り最小の部分文字列である空の文字列に逆戻りします。このようにして、私の条件が初めて真になると、それを満たす最大の部分文字列になります。

必要に応じて逆の方向に進むこともできますが、これまでに条件を満たす最長の部分文字列の長さを保存する変数を導入する必要があります。

public static String findLongestPrefixSuffix(String s1, String s2) {

   if (s1.equals(s2)) { // this part is optional and will 
      return s1;        // speed things up if s1 is equal to s2
   }                    //

   int max = 0;
   for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
      if (s2.endsWith(s1.substring(0, i))) {
         max = i;
      }
   }
   return s1.substring(0, max);
}

記録として:i = 1後者の例から始めて、パフォーマンスを少し向上させることができます。これに加えiて、サフィックスが少なくとも取得したい長さを指定するために使用できます。;) 書くと、見つかった部分文字列の最大長を指定するためにMath.min(s1.length(), s2.length()) - x使用できます。xこれらのことはどちらも最初のソリューションでも可能ですが、最小の長さはもう少し複雑です。;)

あなたの質問のパート1

上記の部分で、コードの作成者はの最後の文字が であるCollections.reverseすべての位置を検索し、この位置を保存します。s1s2

以下は、基本的に私のアルゴリズムが行うことです。違いは、すべての部分文字列をチェックするのではなく、最後の文字s2.

これは、速度を上げるためのある種の最適化です。速度がそれほど重要でない場合は、私の素朴な実装で十分です。;)

于 2013-10-20T18:59:28.327 に答える
3

その解決策はどこで見つけましたか？信頼できる、尊敬されているコーダーによって書かれましたか? それがよくわからない場合は、読む価値がないかもしれません。非常に単純なことを達成するために、非常に複雑で非効率的なコードを書くことができ、アルゴリズムを理解する価値はありません。

誰かの解決策を理解しようとするよりも、自分で考えた方が簡単かもしれません。そうすることで、問題をよりよく理解し、ロジックが自分のものになると思います。時間と練習を重ねるうちに、思考プロセスはより自然になり始めます。練習は完璧を作る。

とにかく、ここでは Python でより単純な実装を行います(ネタバレ注意!)。最初に自分で解決策を見つけ出し、後でそれを私のものと比較することをお勧めします。

于 2013-10-19T22:43:19.427 に答える
2

アパッチコモンズ lang3, StringUtils.getCommonPrefix()

Java は、stdlib を介して有用なものを提供するのが本当に苦手です。良い面としては、ほとんどの場合、Apache から妥当なツールが提供されています。

于 2016-04-12T12:01:31.450 に答える