Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

countHi challenge

Posted on 2016-09-09
25
Medium Priority
?
216 Views
Last Modified: 2016-09-15
Hi,

I am working on below challenge
http://codingbat.com/prob/p184029

Given a string, compute recursively (no loops) the number of times lowercase "hi" appears in the string.

countHi("xxhixx") → 1
countHi("xhixhix") → 2
countHi("hi") → 1
i was not clear on how to find the number of hi using recursion? please advise
0
Comment
Question by:gudii9
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 11
  • 7
  • 3
  • +2
25 Comments
 
LVL 16

Expert Comment

by:gurpsbassi
ID: 41791977
This question and all the previous ones you have littered EE with could be solved by you if you take the time to read up on recursion. Warning....if you found if/else statements difficult, this will blow your mind!
1
 
LVL 28

Accepted Solution

by:
rrz earned 1000 total points
ID: 41792702
This challenge is different from the most of the recursion challenges that you posted.
But, it the same exact programming  problem as
https://www.experts-exchange.com/questions/28968900/countX.html
They use a couple of methods of the String class.  Do you know which ones ?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41793543
Substring,consist Of
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 28

Expert Comment

by:rrz
ID: 41793628
I used substring and indexOf.
0
 
LVL 32

Assisted Solution

by:awking00
awking00 earned 500 total points
ID: 41794636
You could also use substring and startsWith.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41796851
psedi code:
1. if length is zero return 0
2. if length is 1 return 0
3. else if str starts with h and substring with next character is equals to hi then rerun same recursive function by giving length minus one
4. return hi count.
public int countHi(String str) {
  if(str.length()==0) return 0;
  if(str.length()==1) return 1;
  if(str.startsWith("h")&&str.substring(i,i+1).equals("hi")){
  return  1+countHi(str.length()-1);
  }
}



//substring and startsWith.

Open in new window

i tried as above
Compile problems:


Error:      if(str.startsWith("h")&&str.substring(i,i+1).equals("hi")){
                                            ^
i cannot be resolved


see Example Code to help with compile problem
getting above error.
i do not want to use i and for loop for this but only recursion approach? please advise
0
 
LVL 28

Expert Comment

by:rrz
ID: 41796950
I think it would be easier to do this like I solved
https://www.experts-exchange.com/questions/28968900/countX.html
0
 
LVL 7

Author Comment

by:gudii9
ID: 41796958
public int countHi(String str) {
   if (str.length() <2){ 
	    	return 0;
	    		}
	    if (str.substring(0,2).equals( "hi")) {
	    	return 1 + countHi(str.substring(1));
	    	}
	    	else {
		   return countHi(str.substring(1));
	    	  
	    	}
	
	}




//substring and startsWith.

Open in new window


above passed all tests. any alternate approaches or improvements?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41796960
public int countHi(String str) {
   if (str.length() <2){ 
	    	return 0;
	    		}
	    if (str.substring(0,2) == "hi") {
	    	return 1 + countHi(str.substring(1));
	    	}
	    	else {
		   return countHi(str.substring(1));
	    	  
	    	}
	
	}




//substring and startsWith.

Open in new window


why with == it failse below tests?
Expected      Run            
countHi("xxhixx") → 1      0      X      
countHi("xhixhix") → 2      0      X      
countHi("hi") → 1      1      OK      
countHi("hihih") → 2      0      X      
countHi("h") → 0      0      OK      
countHi("") → 0      0      OK      
countHi("ihihihihih") → 4      0      X      
countHi("ihihihihihi") → 5      0      X      
countHi("hiAAhi12hi") → 3      0      X      
countHi("xhixhxihihhhih") → 3      0      X      
countHi("ship") → 1      0      X      
other tests
OK      
0
 
LVL 28

Expert Comment

by:rrz
ID: 41797012
why with == it failse below tests?
Don't use ==  to compare Strings. It checks  if one object is equal to the other.  In this case, they are different objects. But they do have same contents. Always use the equals method to compare String content.
0
 
LVL 28

Expert Comment

by:rrz
ID: 41797015
Here is my solution.
public int countHi(String str) {
  int index = str.indexOf("hi");
  if(index == -1) return 0;
  else return 1 + countHi(str.substring(index + 2));
}

Open in new window

0
 
LVL 37

Assisted Solution

by:zzynx
zzynx earned 500 total points
ID: 41797359
Replace this code
    if (str.substring(0,2) == "hi") {
	  return 1 + countHi(str.substring(1));
    }

Open in new window


by this:
    if ("hi".equals(str.substring(0,2)) {
	  return 1 + countHi(str.substring(2));
    }

Open in new window


That are two improvements:
1) using equals instead of == (never do that for strings)
2) If you know that str.substring(0,2) equals "hi", you can start searching for antoher "hi" at index 2.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41798204
 if (str.substring(0,2).equals( "hi")) {

how above different from below
  if ("hi".equals(str.substring(0,2)) {

Open in new window


to me both seems same?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41798217
public int countHi(String str) {
   if (str.length() <2){ 
	    	return 0;
	    		}
	    if (str.substring(0,2).equals( "hi")) {
	    	return 1 + countHi(str.substring(1));
	    	}
	    	else {
		   return countHi(str.substring(1));
	    	  
	    	}
	
	}




//substring and startsWith.

Open in new window


is recursion bit inefficient approach as we are checking inside if and also again inside else block each character?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41798225
2) If you know that str.substring(0,2) equals "hi", you can start searching for antoher "hi" at index 2.

i was not clear on above point? can you please elaborate on how at index 2 another "hi"?( i thought we search next character then again next character..till end)
0
 
LVL 32

Expert Comment

by:awking00
ID: 41798368
Although it can be done with either the indexOf or startsWith function, I'm going to use startsWith as I think it's a little easier to visualize.
Think about what is happening. Assume str = "xhixhix"
since the length >= 2, the program goes to the next if statement
Since the str does not start with "hi", it goes to the next if
which is return countHi(str.substring(1)) which is now the string "hixhix"
now its does start with "hi" so we add 1 to the substring from index 1 would now be ixhix but since it found "hi" during the last method call, you know that the character at the next index has to be "i" so the next substring should start at index 2 making it "xhix" which doesn't start with "hi" so get the next substring from index 1 which is hix that does start with "hi" so we add 1 to the following substring at index 2 is "x" which has a length less than 2 so 0 is returned and we are done.
0
 
LVL 28

Expert Comment

by:rrz
ID: 41798409
I think using indexOf  makes more sense. If the input was
"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxhi"  
then it would be much more efficient.
0
 
LVL 32

Expert Comment

by:awking00
ID: 41798457
rrz, I totally agree that using indexOf would likely be more efficient. I was just trying to get gudii9 to see what's happening to the strings with each recursion and thought startsWith might make it a little easier to understand.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41798472
why with == it failse below tests?
Don't use ==  to compare Strings. It checks  if one object is equal to the other.  In this case, they are different objects. But they do have same contents

how in this case they are different objects?


That are two improvements:
1) using equals instead of == (never do that for strings)
2) If you know that str.substring(0,2) equals "hi", you can start searching for antoher "hi" at index 2.

i think i got above points

public int countHi(String str) {
   if (str.length() <2){ 
	    	return 0;
	    		}
 if (str.substring(0,2).equals( "hi")) {//does it make difference reverse if ("hi".substring(0,2).equals(str))??
	    	return 1 + countHi(str.substring(2));
	    	}
	    	else {
		   return countHi(str.substring(1));
	    	  
	    	}
	
	}




//substring and startsWith.

Open in new window

0
 
LVL 7

Author Comment

by:gudii9
ID: 41798477
what is psedo code for startsWith?
1. check given string startsWith "hi"
2. if yes then 1+countHi(2)
3. else countHi(2)
4. then return count?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41798480
public int countHi(String str) {
   if (str.length() <2){ 
	    	return 0;
	    		}
	    if (str.startsWith( "hi")) {
	    	return 1 + countHi(str.substring(2));
	    	}
	    	else {
		   return countHi(str.substring(1));
	    	  
	    	}
	
	}




//substring and startsWith.

Open in new window


like above. Above passes all tests. Any improvement in above approach?
0
 
LVL 37

Expert Comment

by:zzynx
ID: 41799242
str.startsWith( "hi")

Open in new window

or
str.substring(0,2).equals( "hi")

Open in new window

or
"hi".equals(str.substring(0,2))

Open in new window


All do the same: checking if the first two characters of str are "hi".

It's safer to write
"hi".equals(str.substring(0,2))

Open in new window

than
str.substring(0,2).equals( "hi")

Open in new window

because if str = null the first will lead to a NullPointerException while the second will just work as expected.
0
 
LVL 28

Expert Comment

by:rrz
ID: 41799266
@zzynx,   I think you got that last sentence backwards.
0
 
LVL 37

Expert Comment

by:zzynx
ID: 41799288
@rrz: Right you are of course. :-)

Let me correct that:
...because if str = null
str.substring(0,2).equals( "hi")

Open in new window

will lead to a NullPointerException while
"hi".equals(str.substring(0,2))

Open in new window

will just work as expected.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41799835
i got it. Thank you for reinforcing the knowledge
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will inform Clients about common and important expectations from the freelancers (Experts) who are looking at your Gig.
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

618 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