utsav: It works fine, I did little bug fixing on boundaries as here goes :
bool IsValid(string s)
{
for(int len=1;len<=s.size()/2;len++)
{
int start1=0,start2=len;
while(start2<s.size())
{
int i=0;
for(;i<len && start2+i<s.size() && s[start1+i]==s[start2+i];i++);
if(i>=len)
return false; //"not valid"
start1++;
start2++;
}
}
return true; // valid
}
It works for both input you provided. :)
On Mon, Jun 4, 2012 at 8:14 AM, utsav sharma <[email protected]>wrote:
> @jeevitesh :- yes i am also thinking of suffix tree,
> but i am facing problem in implementing it. did you implement it ??
>
>
> On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma <[email protected]>wrote:
>
>> @hassan :- it will not work for many strings as you are checking from the
>> mid of strings. try out "ababcdef","aabc".
>> @atul :- it should be done in O(n).
>>
>>
>> On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared <[email protected]>wrote:
>>
>>> yes it's not valid
>>>
>>>
>>> On Sun, Jun 3, 2012 at 5:36 PM, anugrah <[email protected]>wrote:
>>>
>>>> So any string with two same characters is not valid??
>>>>
>>>> for example :
>>>>
>>>> GEEK has E followed by E.
>>>>
>>>> So GEEK is also invalid?
>>>>
>>>> On Jun 3, 1:49 pm, Hassan Monfared <[email protected]> wrote:
>>>> > bool IsValid(string s)
>>>> > {
>>>> > for(int len=0;len<s.len/2;len++)
>>>> > {
>>>> > int start1=0,start2=len+1;
>>>> > while(start2<s.size())
>>>> > {
>>>> > for(int i=0;i<len && start2+i<s.size() &&
>>>> > s[start1+i]=s[start2+i];i++);
>>>> > if(i==len)
>>>> > return false; //"not valid"
>>>> > start1++;
>>>> > start2++;
>>>> > }
>>>> > }
>>>> > return true; // valid
>>>> >
>>>> >
>>>> >
>>>> >
>>>> >
>>>> >
>>>> >
>>>> > }
>>>> > On Sun, Jun 3, 2012 at 12:52 PM, atul anand <[email protected]>
>>>> wrote:
>>>> > > can be done with O(n^2) time complexity..
>>>> >
>>>> > > can it be done with O(n) complexity ???
>>>> >
>>>> > > On 6/3/12, utsav sharma <[email protected]> wrote:
>>>> > > > given a string tell wether it is valid or not.
>>>> > > > string is valid if there is no substring which have the same
>>>> substring
>>>> > > > following it.
>>>> >
>>>> > > > these strings are not valid:- "stringstring","geek123123rt",
>>>> > > > "abcadabcad","strngstingstrngsting"
>>>> >
>>>> > > > --
>>>> > > > You received this message because you are subscribed to the
>>>> Google Groups
>>>> > > > "Algorithm Geeks" group.
>>>> > > > To post to this group, send email to [email protected].
>>>> > > > To unsubscribe from this group, send email to
>>>> > > > [email protected].
>>>> > > > For more options, visit this group at
>>>> > > >http://groups.google.com/group/algogeeks?hl=en.
>>>> >
>>>> > > --
>>>> > > You received this message because you are subscribed to the Google
>>>> Groups
>>>> > > "Algorithm Geeks" group.
>>>> > > To post to this group, send email to [email protected].
>>>> > > To unsubscribe from this group, send email to
>>>> > > [email protected].
>>>> > > For more options, visit this group at
>>>> > >http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
