問題タブ [palindrome]

目標: あらゆる言語。文字列が回文かどうかを返す最小の関数。これがPythonの私のものです:

50文字。

受け入れられた回答は、現在の最小のものになります。これは、より小さなものが見つかると変化します。コードの言語を指定してください。

それは私が答えることができなかったインタビューの質問でした：

正規表現を使用して文字列が回文であることを確認するにはどうすればよいですか？

ps「与えられた文字列が回文であるかどうかを確認する方法」という質問がすでにあり、さまざまな言語で多くの回答が得られますが、正規表現を使用した回答はありません。

Jon Limjap のインタビュー事故に興味を持ち、回文検出を効率的に行う方法を探し始めました。回文ゴルフの回答を確認しましたが、回答には 2 つのアルゴリズムのみがあり、文字列を逆にして、テールとヘッドからチェックしているように思えます。

これらの方法はどちらも、巨大な DNA 配列の正確なパリンドロームの検出には使用されていないと思います。少し調べてみましたが、これを行うための非常に効率的な方法についての無料の記事は見つかりませんでした。

良い方法は、最初のバージョンを分割統治法で並列化し、char 配列 1..n と length-1-n..length-1 のペアを各スレッドまたはプロセッサに割り当てることです。

より良い方法は何でしょうか？

何でも知ってますか？

Python を使用して、Project Eulerの問題の4 番目の問題を解決しようとしています。誰かが私が間違っていることを教えてもらえますか? 問題は、2 つの 3 桁の数の積から作られる最大の回文を見つけることです。これが私がこれまでに持っているものです。

プログラムに問題があります。回文をスタック経由で認識するプログラムである必要があります。すべてがうまく機能しますが、機能しないのは、機能が完了した後にスタック (元と逆) を印刷することだけです。これが私のコード全体であり、問​​題はケースdとeにあります:

整数の2進表現が回文であるかどうかを確認するにはどうすればよいですか？

文字列が回文かどうかを検出する再帰関数を作成するのに助けが必要です。しかし、再帰的でなければならないループは使用できません。誰でもこれがどのように行われるかを教えてくれますか? 私はPythonを使用しています。

たとえば、文字列「abaccddccefe」の「ccddcc」

解決策を考えましたが、O(n^2)時間で実行されます

アルゴリズム 1:

手順: 力ずくの方法

1. 
   i = 1 から i が array.length 未満の場合は2 つの for ループを持ち
   、j=i+1 から j が array.length 未満の場合は -1
2. このようにして、配列から可能なすべての組み合わせの部分文字列を取得できます
3. 文字列が回文かどうかをチェックする回文関数を用意する
4. したがって、すべての部分文字列 (i,j) に対してこの関数を呼び出し、回文の場合は文字列変数に格納します
5. 次の回文部分文字列が見つかった場合、それが現在のものよりも大きい場合は、現在のものに置き換えます。
6. 最後に、文字列変数に答えがあります

問題: 1. このアルゴリズムは O(n^2) 時間で実行されます。

アルゴリズム 2:

1. 文字列を反転し、別の配列に格納します
2. 両方の配列間で一致する最大の部分文字列を見つけます
3. しかし、これも O(n^2) 時間で実行されます

より良い時間で実行されるアルゴリズムを考えてもらえますか? できればO(n)時間

私は Project Euler Problem 4に取り組んでおり、2 3 桁の数の積の回文を見つける必要があるため、次のように思いつきました。

これが機能しないのはなぜですか? どうすれば機能させることができますか? どういうわけか答えをリストに入れて、それが回文であるかどうかを逆にしてチェックする必要があると思います。

c ++で、与えられた15桁の数字の次の回文を見つけるための最速のロジックは何ですか? たとえば、134567329807541 の次の回文は何になりますか?