Solved

strDist challenge

Posted on 2016-09-23
35
84 Views
Last Modified: 2016-10-01
Hi,

I am working on below challenge.
http://codingbat.com/prob/p195413
Psedo code:
1. find length of str starting and ending with sub.
2. return the length

I wrote my code as below and not passing all tests
public int strDist(String str, String sub) {
   if (str.length() <2){ 
	    	return 0;
	    		}
	    if (str.startsWith( sub) {
	    	return 1 + strDist(str.substring(2));
	    	}
	    	else {
		   return strDist(str.substring(1));
	    	  
	    	}
}

Open in new window

i am getting below error

Compile problems:


Error:      return 1 + strDist(str.substring(2));
                 ^^^^^^^
The method strDist(String, String) in the type Shell is not applicable for the arguments (String)


see Example Code to help with compile problems
Any improvements or alternate approaches?      

please advise
0
Comment
Question by:gudii9
  • 21
  • 11
  • 3
35 Comments
 
LVL 7

Author Comment

by:gudii9
ID: 41813362
please advise
0
 
LVL 7

Author Comment

by:gudii9
ID: 41813369
public int strDist(String str, String sub) {
   if (str.indexOf(sub) == -1) return 0;
    if (str.substring(0, sub.length()).equals(sub)
            && str.substring(str.length() - sub.length())
            .equals(sub)){
        return str.length();
            }
    else (! str.substring(0, sub.length() ).equals(sub) ){
        return strDist(str.substring(1), sub);
    }
    

}

Open in new window


above gives below error

Compile problems:


Error:      else (! str.substring(0, sub.length() ).equals(sub) ){
                                                          ^
Syntax error, insert "AssignmentOperator ArrayInitializer" to complete ArrayInitializerAssignement


see Example Code to help with compile problems

please advise
0
 
LVL 32

Accepted Solution

by:
sarabande earned 250 total points
ID: 41814768
your compilation errors are because of calling the strDist with one string argument. but it requires two: one the string to analyze. one the sub string that should match begin and end of the first given string.

recursion would be done by checking the input string whether it starts and ends with the sub string. if that is true, you return length of string.

if not, and neither begin and end matches to the substring, you recursively call strDist by changing the first string argument to a substring where the first and last  character of the given string was erased.

if not, and only begin matches to substring (but end does not), you recursively call strDist with a string that was shortened by one character.

if not, and only end matches to substring (but begin does not), you recursively call strDist with a string where the first character was eliminated.

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41815256
public int strDist(String str, String sub) {
   if (str.indexOf(sub) == -1) return 0;
    if (str.substring(0, sub.length()).equals(sub)
            && str.substring(str.length() - sub.length())
            .equals(sub)){
        return str.length();
            }
    else if(! str.substring(0, sub.length() ).equals(sub) ){
        return strDist(str.substring(1), sub);
    }
  
  else return 1000;
}

Open in new window


i had condition in else which is wrong

above gives below errors


Expected      Run            
strDist("catcowcat", "cat") → 9      9      OK      
strDist("catcowcat", "cow") → 3      1000      X      
strDist("cccatcowcatxx", "cat") → 9      1000      X      
strDist("abccatcowcatcatxyz", "cat") → 12      1000      X      
strDist("xyx", "x") → 3      3      OK      
strDist("xyx", "y") → 1      1000      X      
strDist("xyx", "z") → 0      0      OK      
strDist("z", "z") → 1      1      OK      
strDist("x", "z") → 0      0      OK      
strDist("", "z") → 0      0      OK      
strDist("hiHellohihihi", "hi") → 13      13      OK      
strDist("hiHellohihihi", "hih") → 5      1000      X      
strDist("hiHellohihihi", "o") → 1      1000      X      
strDist("hiHellohihihi", "ll") → 2      1000      X      
other tests
X      
0
 
LVL 7

Author Comment

by:gudii9
ID: 41815272
public int strDist(String str, String sub) {
   if (str.indexOf(sub) == -1) return 0;
    if (str.substring(0, sub.length()).equals(sub)
            && str.substring(str.length() - sub.length())
            .equals(sub)){
        return str.length();
            }
    else if(! str.substring(0, sub.length() ).equals(sub) ){
        return strDist(str.substring(1), sub);
    }
  
  else if(! str.substring( str.length()-sub.length() ).equals(sub) ){
        return strDist(str.substring(0,str.length()-1), sub);
}
else return 1000;

}

Open in new window


above passes all tests.

any improvements or alternate approaches.

Basically pesedo code:

1. check first few letter same as sub and also last few letters same as sub if true return big string length
2. if first few letters are same as sub then do recursion of same method by passing one less character from front of big string along with sub
3. if last few letters are same as sub then do recursion of same method by passing one less character from back along with sub
0
 
LVL 27

Assisted Solution

by:rrz
rrz earned 250 total points
ID: 41815304
Here is my recursion code. But, it only uses recusion to do the trimming. Maybe that is cheating.
public int strDist(String str, String sub) {
  if(str.length() < sub.length())return 0;
  if(!str.startsWith(sub))return strDist(str.substring(1), sub);
  if(!str.endsWith(sub))return strDist(str.substring(0, str.length() - 1), sub);
  return str.length();
}

Open in new window

 and here is a simpler code(without recursion).
public int strDist(String str, String sub) {
  if(str.indexOf(sub) == -1)return 0;
  return str.lastIndexOf(sub) - str.indexOf(sub) + sub.length();
}

Open in new window

0
 
LVL 32

Expert Comment

by:sarabande
ID: 41816014
any improvements or alternate approaches.
to avoid repeating statements you could do:

int len = str.length();
if (str.startsWith(sub)&&str.endsWith(sub) );
{
     return len;
}
int pos = str.indexOf(sub);
if (pos == -1)    
      return 0;
if (pos > 0)
{
     return StrDist(str.substring(pos), sub);
}

return StrDist(str.substring(0, len-1), sub);

Open in new window


note, you should return 0 if the string doesn't contain the sub string.

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41816259
i like above approach with pos and also starts and endwith

what would be pos value  for last return. when does it goes into below statement

return StrDist(str.substring(0, len-1), sub);

Open in new window


is it pos<0 but -1 is already covered above?
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41816515
the return value is the length of the maximum string that begins with sub and ends with sub.

the final return is when both the begin and the end are matching or when the sub is not in str at all. for the last case you should return -1 or 0. both these values would indicate failure since otherwise the smallest return value is length of sub.

pos < 0 must be checked to find out whether str contains at least one occurrance of sub. for all further calls this is redundant. same the indexOf is onl used in the first call but not later.

because of that you could optimize like that:

int StrDist(String str, int lensub)
{
     int len = str.length();
     if (str.endsWith(str.substring(0, lensub)))
     {
           return len;
     }
     return StrDist(str.substring(0, len-1), lensub)
}

int StrDist(String str, String sub)
{
    int pos = str.indexOf(sub);
    if (pos == -1)    
        return 0;
    str = str,substring(pos);
    return StrDist(str, sub.length());  // calls the first StrDist function
}

Open in new window


the first StrDist function expects a string and a length, and only checks whether the left tail of str is equal to the right tail. this function is the one that was called recursively.

the second StrDist is the initial call where we check whether the sub is in the string at all and where the first position is. for all further calls the string only would be changed at the right.

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41817986
int StrDist(String str, int lensub)
{
     int len = str.length();
     if (str.endsWith(str.substring(0, lensub)))
     {
           return len;
     }
     return StrDist(str.substring(0, len-1), lensub)
}

int StrDist(String str, String sub)
{
    int pos = str.indexOf(sub);
    if (pos == -1)    
        return 0;
    str = str,substring(pos);
    return StrDist(str, sub.length());  // calls the first StrDist function
}

Open in new window


above gives below error

Compile problems:


Error:      return StrDist(str.substring(0, len-1), lensub)
                                                    ^
Syntax error, insert ";" to complete ReturnStatement


see Example Code to help with compile problems


please advise
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41818310
Syntax error, insert ";" to complete ReturnStatement

the compiler told you what to do.

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41818316
int StrDist(String str, int lensub)
{
     int len = str.length();
     if (str.endsWith(str.substring(0, lensub)))
     {
           return len;
     }
     return StrDist(str.substring(0, len-1), lensub);
}

int StrDist(String str, String sub)
{
    int pos = str.indexOf(sub);
    if (pos == -1)    
        return 0;
    str = str,substring(pos);
    return StrDist(str, sub.length());  // calls the first StrDist function
}

Open in new window

i fixed that and then i got below error
Compile problems:


Error:      str = str,substring(pos);
               ^
Syntax error on token ",", ; expected


see Example Code to help with compile problems

now
int StrDist(String str, int lensub)
{
     int len = str.length();
     if (str.endsWith(str.substring(0, lensub)))
     {
           return len;
     }
     return StrDist(str.substring(0, len-1), lensub);
}

int StrDist(String str, String sub)
{
    int pos = str.indexOf(sub);
    if (pos == -1)    
        return 0;
    str = str.substring(pos);
    return StrDist(str, sub.length());  // calls the first StrDist function
}

Open in new window


above gives below error
Compile problems:


Error:The method strDist(String, String) is undefined

see Example Code to help with compile problems


please advise.
i saw above method though? not sure why compiler complaining
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41818345
str = str,substring(pos);
didn't you see that it is a comma left of substring. did you ever encounter a comma left of substring? again, the Compiler told you what is wrong.

you really could read the compiler errors. and when taking them literally, you have a good chance to correct the errors by your own...

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41818381
yes I corrected comma with . error.

now I got new error like method not defined
int StrDist(String str, int lensub)
{
     int len = str.length();
     if (str.endsWith(str.substring(0, lensub)))
     {
           return len;
     }
     return StrDist(str.substring(0, len-1), lensub);
}

int StrDist(String str, String sub)
{
    int pos = str.indexOf(sub);
    if (pos == -1)    
        return 0;
    str = str.substring(pos);
    return StrDist(str, sub.length());  // calls the first StrDist function
}

Open in new window

Compile problems:


Error:The method strDist(String, String) is undefined



see Example Code to help with compile problems


I think recursion method needs string and int as argument
int StrDist(String str, int lensub)


where as the method defined has String and String as arguents?

int StrDist(String str, String sub)
0
 
LVL 7

Author Comment

by:gudii9
ID: 41818386
when I changed second argument from string to int getting different error
int StrDist(String str, int lensub)
{
     int len = str.length();
     if (str.endsWith(str.substring(0, lensub)))
     {
           return len;
     }
     return StrDist(str.substring(0, len-1), lensub);
}

int StrDist(String str, int lensub)
{
    int pos = str.indexOf(sub);
    if (pos == -1)    
        return 0;
    str = str.substring(pos);
    return StrDist(str, sub.length());  // calls the first StrDist function
}

Open in new window


saying duplicate method


Error:      int StrDist(String str, int lensub)
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Duplicate method StrDist(String, int) in type Shell
0
 
LVL 7

Author Comment

by:gudii9
ID: 41818392
int StrDist(String str, int lensub)
{
     int len = str.length();
     if (str.endsWith(str.substring(0, lensub)))
     {
           return len;
     }
     return StrDist(str.substring(0, len-1), lensub);
}

int StrDist(String str2, int lensub2)
{
    int pos = str.indexOf(sub);
    if (pos == -1)    
        return 0;
    str = str.substring(pos);
    return StrDist(str, sub.length());  // calls the first StrDist function
}

Open in new window


changing variable names did not help due to elbow same error

Compile problems:


Error:      int StrDist(String str, int lensub)
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Duplicate method StrDist(String, int) in type Shell




see Example Code to help with compile problems
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41818801
Error:The method strDist(String, String) is undefined
don't know enough of java whether it allows same function name and different arguments.

you better go back to the last solution which passes all tests with one StrDist function taking two String arguments.

Sara
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 27

Expert Comment

by:rrz
ID: 41818969
I think you somehow lost your way on this.  Let's go back to what Sara posted above here  at
https://www.experts-exchange.com/questions/28971911/strDist-challenge.html#a41816014    
The only mistakes were wrongly capitalize the method name and added a semi-colon where it didn't belong. If we correct those mistakes, then it works ok.
public int strDist(String str, String sub) {
  int len = str.length();
  if (str.startsWith(sub)&&str.endsWith(sub) ){
     return len;
  }
  int pos = str.indexOf(sub);
  if (pos == -1)     return 0;
  if (pos > 0){
     return strDist(str.substring(pos), sub);
  }
  return strDist(str.substring(0, len-1), sub);
}

Open in new window

  My code is  at  
https://www.experts-exchange.com/questions/28971911/strDist-challenge.html#a41815304
0
 
LVL 7

Author Comment

by:gudii9
ID: 41819036
How to make code approach in ID: 41816515 to make it work as it gives below error


int StrDist(String str, int lensub)
{
     int len = str.length();
     if (str.endsWith(str.substring(0, lensub)))
     {
           return len;
     }
     return StrDist(str.substring(0, len-1), lensub);
}

int StrDist(String str2, int lensub2)
{
    int pos = str.indexOf(sub);
    if (pos == -1)    
        return 0;
    str = str.substring(pos);
    return StrDist(str, sub.length());  // calls the first StrDist function
}

Select all
 
Open in new window

changing variable names did not help due to elbow same error

Compile problems:


Error:      int StrDist(String str, int lensub)
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Duplicate method StrDist(String, int) in type Shell

Open in new window


Is above approach is fixable?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41819037
public int strDist(String str, String sub) {
  int len = str.length();
  if (str.startsWith(sub)&&str.endsWith(sub) ){//if start and end with sub simply returning str lenght //which makes sense
     return len;
  }
  int pos = str.indexOf(sub);
  if (pos == -1)     return 0;//if no sub returning 0 which is ok
  if (pos > 0){//if sub i.e pos is positive number exist then returning recursive function call till reaches //which base case??
     return strDist(str.substring(pos), sub);
  }
  return strDist(str.substring(0, len-1), sub);//when (at what condition  like pos==0??)does control comes here??
}

Open in new window

0
 
LVL 27

Expert Comment

by:rrz
ID: 41819043
How to make code approach in ID: 41816515 to make it work as it gives below error
I don't know. That is  Sara's code.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41819045
looks like that is not possible. I tried many ways but could not make it to work
0
 
LVL 7

Author Comment

by:gudii9
ID: 41819048
public int strDist(String str, String sub) {
   if (str.indexOf(sub) == -1) return 0;
    if (str.substring(0, sub.length()).equals(sub)
            && str.substring(str.length() - sub.length())
            .equals(sub)){
        return str.length();
            }
    else if(! str.substring(0, sub.length() ).equals(sub) ){
        return strDist(str.substring(1), sub);
    }
  
  else if(! str.substring( str.length()-sub.length() ).equals(sub) ){
        return strDist(str.substring(0,str.length()-1), sub);
}
else return 1000;

}

Open in new window


how my above approach is different from your below approach?
public int strDist(String str, String sub) {
  int len = str.length();
  if (str.startsWith(sub)&&str.endsWith(sub) ){//if start and end with sub simply returning str lenght //which makes sense
     return len;
  }
  int pos = str.indexOf(sub);
  if (pos == -1)     return 0;//if no sub returning 0 which is ok
  if (pos > 0){//if sub i.e pos is positive number exist then returning recursive function call till reaches //which base case??
     return strDist(str.substring(pos), sub);
  }
  return strDist(str.substring(0, len-1), sub);//when (at what condition  like pos==0??)does control comes here??
}

Open in new window

0
 
LVL 32

Expert Comment

by:sarabande
ID: 41819232
how my above approach is different from your below approach?
the second code
- avoids to have the same function call, for example strlen, twice.
- uses functions startsWith and endsWith
- uses the start position of the first occurrence of sub for the next substring to pass.
   this spares some recursive calls if sub is not at position 0 or position 1.
- returns 0 if sub is not contained in str what is well-defined while returning 1000 is not.

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41821006
returns 0 if sub is not contained in str what is well-defined
i was not clear on above. can you please elaborate?
Are you referring below line
return strDist(str.substring(0, len-1), sub);

and the zero above?
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41821192
no, i was referring to

   return 1000;

of your code what is not well defined compared to

   if (pos == -1)     return 0;

what would return length = 0 if sub was not contained into str.

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41821818
public int strDist(String str, String sub) {
   if (str.indexOf(sub) == -1) return 0;
    if (str.substring(0, sub.length()).equals(sub)
            && str.substring(str.length() - sub.length())
            .equals(sub)){
        return str.length();
            }
    else if(! str.substring(0, sub.length() ).equals(sub) ){
        return strDist(str.substring(1), sub);
    }
  
 /* else if(! str.substring( str.length()-sub.length() ).equals(sub) ){
        return strDist(str.substring(0,str.length()-1), sub);
}*/
else return strDist(str.substring(0,str.length()-1), sub);

}

Open in new window


above passes all tests as well.

i moved else if code to else
0
 
LVL 7

Author Comment

by:gudii9
ID: 41821878
public int strDist(String str, String sub) {
  int len = str.length();
  if (str.startsWith(sub)&&str.endsWith(sub) ){//if start and end with sub simply returning str lenght //which makes sense
     return len;
  }
  int pos = str.indexOf(sub);
  if (pos == -1)     return 0;//if no sub returning 0 which is ok
  if (pos > 0){//if sub i.e pos is positive number exist then returning recursive  function call till reaches //which base case??
     return strDist(str.substring(pos), sub);
  }
  return strDist(str.substring(0, len-1), sub);//when (at what condition  like pos==0??)does control comes here??
}

Open in new window


not clear on above code construct


1. if start and end is sub then  return length
2. if -1 ie sub not found return 0
3. if pos > 0 then doing recursion call again passing shorter string starting from index of sub ie pos and sub
4. else we are calling
 return strDist(str.substring(0, len-1), sub); i was not clear in which case it comes to this last else???
0
 
LVL 7

Author Comment

by:gudii9
ID: 41821894
last else is my biggest confusion in terms of when the code flow reaches there in which scenario?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41821897
in that case why recusion method called by passing str.length()-1 in substring starting from 0??

 return strDist(str.substring(0,str.length()-1), sub);
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41823646
why recusion method called by passing str.length()-1 in substring starting from 0??

since the left side of str alreaydy starts with sub, we only have to shorten the right end until the remaining string ends with sub. note, that would at least be the case when str == sub. then both begin and end matches to sub and returned length is length of sub.

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41823889
since the left side of str alreaydy starts with sub, we only have to shorten the right end until the remaining string ends with sub. note, that would at least be the case when str == sub. then both begin and end matches to sub and returned length is length of sub.

last else is same as below case right?

 else if(! str.substring( str.length()-sub.length() ).equals(sub) ){
        return strDist(str.substring(0,str.length()-1), sub);


you mean like this right


since the left side of str alreaydy not starts with sub, we only have to shorten the right end until the remaining string ends with sub. note, that would at least be the case when str == sub. then both begin and end matches to sub and returned length is length of sub
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41824339
????

1. condition: if (str.startsWith(sub) && str.endsWith(sub) )

that is the final positive case

2. condition: int pos = str.indexOf(sub);   if (pos == -1 )

this is the case when sub is not contained in str (at all). we return 0 length if so.


3. condition: int pos = str.indexOf(sub); .... if (pos > 0)

sub was contained in str but not at the begin. therefore we call recursively a substring of str where we cut the first 'pos' characters.

4. condition: none of the first 3 conditions has applied yet.

therefore str starts with sub and does NOT end with sub (so far).

Sara
0
 
LVL 7

Author Comment

by:gudii9
ID: 41824429
since the left side of str alreaydy starts with sub, we only have to shorten the right end until the remaining string ends with sub. note, that would at least be the case when str == sub. then both begin and end matches to sub and returned length is length of sub.

you mean for below case

strDist("cccatcowcatxx", "cat") → 9
cccatcowcat
so it cuts right to left last xx
then
so above bold becomes 9 length right?
0
 
LVL 32

Expert Comment

by:sarabande
ID: 41824824
so it cuts right to left last xx
the first cut is on the left side. it cuts 'cc' with the first call since pos == 2.

the right cut happens with two recursive calls, each of them cutting one 'x'.

if there was a 'right-find' function we could spare one of these calls.

Sara
0

Featured Post

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

This article will show, step by step, how to integrate R code into a R Sweave document
Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now