It’s a piece of cake. RSSフィード Twitter

2012-12-06 [Python][世界で闘うプログラミング力を鍛える150問]問題1.1

世界で闘うプログラミング力を鍛える150問

せっかく買ったんで、解きながらブログに載せていきます!

これなら手軽にブログ書けるネタになるので、ちょうどいいし。笑。


あ、ちなみに本ではCとC++で実装してますが、

面倒なので基本的にPythonで書いちゃいます。

問題

ある文字列が、すべてユニークである(重複する文字がない)かどうかを判定するアルゴリズムを実装してください。また、それを実装するのに新たなデータ構造が使えない場合、どのようにすればよいですか?


#coding: utf-8


def is_dup_char_in_str(str):
    '''
    文字列中の重複文字チェック関数
    >>> is_dup_char_in_str("hello")
    True
    >>> is_dup_char_in_str("helo")
    False
    >>> is_dup_char_in_str("")
    False
    >>> is_dup_char_in_str("aabcdee")
    True
    '''

    # 引数で渡された文字列中の文字を格納するリスト
    c_list = []

    # 文字列を文字のリストに分解
    for character in str:
        c_list.append(character)

    c_list.sort()

    # 文字リスト中の連続する文字が重複していればTrueを返す
    counter = 0
    while counter < (len(c_list) - 1):
        if c_list[counter] == c_list[counter + 1]:
            return True
        counter = counter + 1

    # 重複が無ければFalseを返す
    return False


def _test():
    import doctest
    doctest.testmod()


if __name__ == '__main__':
    _test()

考察

まずはASCIIUNICODEか確認してから問題に取りかかれとのこと。すみません、検討すらしませんでした^ ^; ちなみにサンプルコードは1バイト前提で、256ビットの配列用意して、文字が重複するかどうかをチェックするってものでした。たしかに1バイトならこれでいいですね。


1問目なんで簡単ですね。

ほいじゃ、シャワー浴びてきます〜☆