UVa : 11362 (Phone List)



// http://uva.onlinejudge.org/external/113/11362.html

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

string nums [10000 + 10];

bool prefix_check (string a, string b)
{
    if ( b.size () < a.size () ) return false;

    for ( size_t i = 0; i < a.length (); i++ ) {
        if ( a [i] != b [i] ) return false;
    }

    return true;
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);

    while ( testCase-- ) {
        int n;
        scanf ("%d", &n);

        for ( int i = 0; i < n; i++ ) cin >> nums [i];

        sort (nums, nums + n);

        bool flag = true;

        for ( int i = 0; i < n - 1; i++ ) {
            if ( prefix_check (nums [i], nums [i + 1]) ) { flag = false; break; }
        }

        if ( flag ) printf ("YES\n");
        else printf ("NO\n");
    }

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

4 thoughts on “UVa : 11362 (Phone List)

  1. would you please describe me about the work of
    for ( size_t i = 0; i < a.length (); i++ ) {
    if ( a [i] != b [i] ) return false;
    } following by

    for ( int i = 0; i < n – 1; i++ ) {
    if ( prefix_check (nums [i], nums [i + 1]) ) { flag = false; break; }
    }

  2. @badhon,
    #35 – #37
    comparing two strings and return false if string a is not a prefix of string b

    that means, if the first portion “b” is equal to the “a” then it will return true

    #57 – #59
    if you sort the phone numbers in order
    then
    all the phone numbers with the same prefix will come together
    and will be place from shorter to longer length

    for example
    unsorted phone numbers

    1234
    123
    124
    12345

    sorted phone numbers

    123
    1234
    12345
    124

    hope it helps 🙂

  3. sorry to disturb u one last time,

    i cannot even understand this part “if ( prefix_check (nums [i], nums [i + 1]) ) { flag = false; break; }” and its work 😦

  4. @badhon
    function prefix_check returns true if 1st parameter is a prefix of 2nd parameter
    if this happens ( prefix_check returns true ) then we don’t need to go further
    that why break; comes in.
    after the loop if (flag == false) then we know, the loop stopped because of the break, not because loop condition statement

    I don’t know If I am making myself clear? If i am not please say so 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s