質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

91.36%

  • Python

    3801questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    2395questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • 正規表現

    565questions

    正規表現とは特定の文字列によるパターンマッチングを行う際に用いられる宣言型プログラミングです。

正規表現を使ったアプローチについて

解決済

回答 1

投稿 2017/11/21 10:27

  • 評価
  • クリップ 0
  • VIEW 75
退会済みユーザー

退会済みユーザー

プログラミング初学者です

https://www.hackerrank.com/challenges/re-findall-re-finditer/problem

例えばこの問題を解こうとしたときに

import re
m = re.findall(r'[^aiueoAIUEO][aiueoAIUEO]{2,}[^aiueoAIUEO]', input())
if len(m) == 0:
        print("-1")
else:
    for i in m:
        print(i[1:-1])


まずこのようなコードで解けると思ったのですが、これだと例えば
abaabaabaabaae
のように探したい文字列が連続したときに後の文字列がアウトプットされないという問題があります

また、同様に
https://www.hackerrank.com/challenges/the-minion-game/problem
この問題を正規表現を使って解けないかと考えたのですが(discussionをチラッと見ると全然使ってはいなかったのですが)、最小単位でfindallを使っても、特定の文字列が見つかると次の文字を読み込んでしまい組み合わせは読み込めないという問題があります

import re

print(re.findall(r'[^AIUEO]+?', input()))

>>['B', 'N', 'N']


正規表現を使うときに、組み合わせをすべて上手く読み取れるようなアプローチがあれば教えていただきたいです
よろしくお願いします

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+1

前半については、すべての母音以外の文字を2つに繰り返してから、findallすればよいかと。
もっとスマートな方法はある可能性が高いですが。

import re
s = input()
cs = set(re.findall(r'[^aiueoAIUEO]', s))
for c in cs:
    s = s.replace(c, c*2)
m = re.findall(r'[^aiueoAIUEO][aiueoAIUEO]{2,}[^aiueoAIUEO]', s)
if len(m) == 0:
        print("-1")
else:
    for i in m:
        print(i[1:-1])

こっちのほうが速いですね。

import re
s = input()
s = re.sub(r'[^aiueoAIUEO]{1,}', 'zz', s)
m = re.findall(r'[^aiueoAIUEO][aiueoAIUEO]{2,}[^aiueoAIUEO]', s)
if len(m) == 0:
        print("-1")
else:
    for i in m:
        print(i[1:-1])

後半は、ただの数え上げなので、正規表現を使わないかと。
例えば、A***なら[A, A*, A**, A***]4種類を数え上げるだけなので。
どうしても全パターンを一度出力したいのならitertoolsのcombinationsを使えば良いです。

import itertools

def list_of_combs(s):
    combs = [s[i:j] for i,j in itertools.combinations(list(range(len(s)))+[None], 2)]
    return combs

print(list_of_combs(input()))
#['B', 'BA', 'BAN', 'BANA', 'BANAN', 'BANANA', 'A', 'AN', 'ANA', 'ANAN', 'ANANA', 'N', 'NA', 'NAN', 'NANA', 'A', 'AN', 'ANA', 'N', 'NA', 'A']

以下チラ裏かもですが。
アルゴリズムに興味があるのかわからないのですが、全パターンを一度展開してしまうと、計算時間・計算メモリともに厳しいものがあります。
計算時間としては計算のオーダーが重要かと思います。

  1. 上の例で、A***を見たら直ちにそれは4を足せば良いと分かればオーダーは文字列の長さにかかわらず1となります。O(1)と表記します。
  2. それに対して[A, A*, A**, A***]と展開すると、文字列の長さM個だけ増えます。これはO(M)というやつです。

この外側に、上の問題の場合文字列の先頭を走査するのに、Sの長さN回行う必要があります。

  1. それぞれの部分文字列の数え上げがO(1)であれば、全体でO(N)、
  2. 部分文字列の数え上げがO(N)であれば、全部合わせて数え上げるのにO(N^2)の計算量がかかります。

問題ではSの長さの上限が10^6でしたので、O(N)のアルゴリズムでは10^6回、O(N^2)のアルゴリズムでは10^12回演算が発生します。
高性能なCPUでも4.5GHzなどなので一秒あたり10^9の演算しかできません。
比較してみると前者のアルゴリズムでは1秒以内に終わるのに対して、後者のアルゴリズムでは数分かかります。

投稿 2017/11/21 11:54

編集 2017/11/21 15:47

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

ただいまの回答率

91.36%

関連した質問

同じタグがついた質問を見る

  • Python

    3801questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    2395questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • 正規表現

    565questions

    正規表現とは特定の文字列によるパターンマッチングを行う際に用いられる宣言型プログラミングです。