题目描述

We know thatif a phone number A is another phone number B’s prefix, B is not able to becalled. For an example, A is 123 while B is 12345, after pressing 123, we callA, and not able to call B.

Given N phone numbers, your task is to find whether there exits two numbers Aand B that A is B’sprefix.

输入

The input consists of several test cases.

 The first line of input in each test case contains one integer N (0<N<1001),represent the number of phone numbers.

 The next line contains N integers, describing the phonenumbers.

 The last case is followed by a line containing one zero.

输出

For each test case, if there exits a phone number thatcannot be called, print “NO”, otherwise print “YES” instead.

示例输入

2

012

012345

2

12

012345

0

示例输出

NO

YES

/*********************

N个字符串中如果有一个是另外一个的前缀，则输出NO，否则输出YES。

O（n^2）的循环，

*********************/

Code:

#include <iostream>

#include<string.h>

#include<stdio.h>

using namespace std;

int main()

{

    char  str[1005][1005];

    char s[1005];

    int n,i,j,li,lj;

    bool leaf;

    while(scanf("%d",&n)&&n)

    {

        leaf  = false;

        li = lj = 0;

        for(i = 0;i<n;i++)

            cin>>str[i];

        for(i = 0;i<n;i++)

        {

            li = strlen(str[i]);

            for(j = 0;j<n;j++)

            {

                lj = strlen(str[j]);

                if(i==j||li>lj)//自己不和自己比较，str[j] 长度比str[i]短的话肯定不是前缀。

                    continue;

                strncpy(s,str[j],li);

                s[li] = '\0';

                if(strcmp(s,str[i])==0)// 发现前缀则跳出循环

                {

                    leaf = true;

                    break;

                }

            }

            if(leaf)

                break;

        }

        if(leaf)

            printf("NO\n");

        else

            printf("YES\n");

    }

    return 0;

}