[プログラマー]ハッシュ-電話番号リスト

4444 ワード
プログラマー高得点球 テキストリンク

プログラマ-電話番号リスト

問題の説明


電話帳の電話番号のうち、1つの番号が別の番号の接頭辞であることを確認します.
接頭辞がある場合はtrueを返し、そうでない場合はfalseを返します.

せいげんじょうけん


phone bookの長さは1以上1000000以下です.
各電話番号の長さは1以上20以下である.

問題を解く


phone bookをソートし、その後の値の接頭辞であることを確認します.
辞書順に並べられているので、次の値を確認するだけです.

コード#コード#

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;

    sort(phone_book.begin(), phone_book.end());

    for(int i=0; i<phone_book.size()-1; i++){
        if (phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size())){
            answer = false;
            break;
        }
    }

    return answer;
}

時間の複雑さ


O(nlogn)

解答時のコメントサイト


mapコンテナのクリーンアップと使用方法
vectorコンテナのクリーンアップと使用方法
JAva同時の集合クラスの不安全問題の深い分析
[アルゴリズム]約数の和