Given a string, compute recursively (no loops) [closed]
Given a string, compute recursively (no loops) the number of times lowercase "hi" appears in the string
countHi("xxhixx") -> 1
countHi("xhixhixx") -> 2
countHi("hi") -> 1
public class Tester {
/**
* @param args
*/
public static void main(String[] args开发者_如何转开发) {
// TODO Auto-generated method stub
int count = countHi("xxhixx");
System.out.println("countHi: " + count);
}
public static int countHi(String s) {
if (s.length() == 0) {
return 0;
}
int spot = s.indexOf("hi");
if(spot > 0)
{
String nextString = s.substring(spot + 2);
return 1 + countHi(nextString);
}
return 1;
}
}
Should work with the following code:
public static int countHi(String s) {
return countHi(s, 0);
}
public static int countHi(String s, int pos) {
if (s.length() - pos < 2) {
return 0;
}
int result = 0;
if(s.charAt(pos) == 'h' && s.charAt(pos + 1) == 'i') {
result++;
}
return result + countHi(s, pos + 2);
}
F(x[1...n]) =
if the string starts with "hi" then 1 + F(x[3...n])
else F(x[2...n])
Your recursive function will need a parameter that tells it where in the string to start looking. If the character at that position is 'h'
, then check whether the one after it is 'i'
; if it is, you've found a match.
For the recursive call that checks the remainder of the string, pass the index of the next character if it wasn't 'i'
, or two characters ahead if it was.
(I'm giving just a description instead of actual code because this looks like a homework question.)
package com.indivunet.utils;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class Tester
{
/**
* @param args
*/
public static void main(String[] args)
{
printCountFor("xxhixx", 1);
printCountFor("", 0);
printCountFor("xxhixxhihi", 3);
printCountFor(null, 0);
}
@Test
public void countHi()
{
assertAndPrint("xxhixx", 1);
assertAndPrint("", 0);
assertAndPrint("xxhixxhihi", 3);
assertAndPrint(null, 0);
}
private void assertAndPrint(String string, int expectedCount)
{
int count = printCountFor(string, expectedCount);
assertEquals(expectedCount, count);
}
private static int printCountFor(String string, int expected)
{
int count = countHi(string);
System.out.println("string: \"" + string + "\" expected: " + expected + " count: " + count);
return count;
}
public static int countHi(String s)
{
if (s == null)
{
return 0;
}
int count = 0;
boolean hiSpotted = true;
while (hiSpotted)
{
int startOfNextHi = s.indexOf("hi");
hiSpotted = startOfNextHi >= 0;
if (!hiSpotted)
{
return count;
}
s = s.substring(startOfNextHi + 2);
count++;
}
return count;
}
}
public static int recCountHi(String str) {
if(str.length() < 2) {
return 0;
}
if(str.substring(0, 2).equals("hi")) {
return 1 + recCountHi(str.substring(1));
}
return recCountHi(str.substring(1));
}
精彩评论