gudii9
asked on
countHi challenge
Hi,
I am working on below challenge
http://codingbat.com/prob/p184029
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.i was not clear on how to find the number of hi using recursion? please advise
countHi("xxhixx") → 1
countHi("xhixhix") → 2
countHi("hi") → 1
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!
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Substring,consist Of
I used substring and indexOf.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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.
i do not want to use i and for loop for this but only recursion approach? please advise
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.
i tried as above Compile problems:getting above error.
Error: if(str.startsWith("h")&&str.substrin g(i,i+1).e quals("hi" )){
^
i cannot be resolved
see Example Code to help with compile problem
i do not want to use i and for loop for this but only recursion approach? please advise
I think it would be easier to do this like I solved
https://www.experts-exchange.com/questions/28968900/countX.html
https://www.experts-exchange.com/questions/28968900/countX.html
ASKER
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.
above passed all tests. any alternate approaches or improvements?
ASKER
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.
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
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.
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));
}
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
if (str.substring(0,2).equals( "hi")) {
how above different from below
if ("hi".equals(str.substring(0,2)) {
to me both seems same?
ASKER
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.
is recursion bit inefficient approach as we are checking inside if and also again inside else block each character?
ASKER
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)
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.
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.
I think using indexOf makes more sense. If the input was
"xxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx xxxxxxxhi"
then it would be much more efficient.
"xxxxxxxxxxxxxxxxxxxxxxxxx
then it would be much more efficient.
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.
ASKER
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.
ASKER
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?
1. check given string startsWith "hi"
2. if yes then 1+countHi(2)
3. else countHi(2)
4. then return count?
ASKER
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.
like above. Above passes all tests. Any improvement in above approach?
str.startsWith( "hi")
orstr.substring(0,2).equals( "hi")
or"hi".equals(str.substring(0,2))
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))
thanstr.substring(0,2).equals( "hi")
because if str = null the first will lead to a NullPointerException while the second will just work as expected.
@zzynx, I think you got that last sentence backwards.
@rrz: Right you are of course. :-)
Let me correct that:
...because if str = null
Let me correct that:
...because if str = null
str.substring(0,2).equals( "hi")
will lead to a NullPointerException while "hi".equals(str.substring(0,2))
will just work as expected.
ASKER
i got it. Thank you for reinforcing the knowledge