CodingBat: Java. Recursion-1, Part III

countPairs:

public int countPairs(String str) {
	if (str.length() < 3) return 0;
	if (str.charAt(0) == str.charAt(2))
		return 1 + countPairs(str.substring(1));
	return countPairs(str.substring(1));
}

countAbc:

public int countAbc(String str) {
	if (str.length() < 3) return 0;
	if (str.substring(0, 3).equals("abc") 
			|| str.substring(0, 3).equals("aba"))
		return 1 + countAbc(str.substring(1));
	return countAbc(str.substring(1));
}

count11:

public int count11(String str) {
	if (str.length() < 2) return 0;
	if (str.substring(0, 2).equals("11"))
		return 1 + count11(str.substring(2));
	return count11(str.substring(1));
}

stringClean:

public String stringClean(String str) {
	if (str.length() < 2) return str;
	if (str.charAt(0) == str.charAt(1))
		return stringClean(str.substring(1));
	return str.charAt(0) + stringClean(str.substring(1));
}

countHi2:

public int countHi2(String str) {
	if (str.length() < 2) return 0;
	if (str.substring(0, 2).equals("hi"))
		return 1 + countHi2(str.substring(2));
	if (str.charAt(0) == 'x' && str.length() >= 3) {
		if (str.substring(1, 3).equals("hi"))
			return countHi2(str.substring(3));
		return countHi2(str.substring(1));
	}
	return countHi2(str.substring(1));
}

parenBit:

public String parenBit(String str) {
	if (!str.substring(0, 1).equals("("))
		return parenBit(str.substring(1));
	return (str.substring(0, str.indexOf(")") + 1));
}

nestParen:

public boolean nestParen(String str) {
	if (str.equals("") || str.equals("()")) return true;
	if (str.charAt(0) == '(' && str.charAt(str.length() - 1) == ')')
		return nestParen(str.substring(1, str.length() - 1));
	return false;
}

strCount:

public int strCount(String str, String sub) {
	if (str.length() < sub.length()) return 0;
	if (str.substring(0, sub.length()).equals(sub))
		return 1 + strCount(str.substring(sub.length()), sub);
	return strCount(str.substring(1), sub);
}

strCopies:

public boolean strCopies(String str, String sub, int n) {
	if (str.length() < sub.length()) return (n <= 0);
	if (str.substring(0, sub.length()).equals(sub))
		return strCopies(str.substring(1), sub, n - 1);
	return strCopies(str.substring(1), sub, n);
}

strDist:

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();
	if (!str.substring(0, sub.length()).equals(sub))
		return strDist(str.substring(1), sub);
	// case: (!str.substring(str.length()-sub.length()).equals(sub))
	return strDist(str.substring(0, str.length() - 1), sub);
}

5 thoughts on “CodingBat: Java. Recursion-1, Part III

  1. Dave Hughes

    I believe strCopies fails when more than n copies are found, where as the challenge called for true when at least n copies were found.

    Simple fix:

    if (str.length() < sub.length()) return (n <= 0);

    Or alternatively, the Coding Bat solution, which short circuits recursion when the target is reached:

    if (n == 0) return true;
    if (str.length() < sub.length()) return false;

    Reply
    1. Gregor Ulm Post author

      Good catch, Dave! I fixed that mistake in my code. The solution on Coding Bat, which I hadn’t looked at previously, is more elegant, and also more efficient.

      Reply
  2. Dana

    Another tested solution for countHi2, a bit less lengthy. 🙂

    public int countHi2(String str) {
    if (str.length() <= 1) return 0;
    if (str.substring(0, 2).equals("hi")) return 1 + countHi2(str.substring(2));
    if (str.charAt(0) == 'x' && str.charAt(1) != 'x') return countHi2(str.substring(2));
    return countHi2(str.substring(1));
    }

    Reply
  3. WOJTEK

    Bit shorter

    public int countAbc(String str) {
    if(str.length()<3) return 0;
    if(str.startsWith("abc") || str.startsWith("aba")) return 1 + countAbc(str.substring(1));
    return countAbc(str.substring(1));
    }

    Reply
  4. WOJTEK

    Shorter

    public int countHi2(String str) {
    if(str.length()<2) return 0;
    if(str.startsWith("xhi")) return countHi2(str.substring(3));
    if(str.startsWith("hi")) return 1 + countHi2(str.substring(2));
    return countHi2(str.substring(1));
    }

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Spammer prevention; the answer is an integer: * Time limit is exhausted. Please reload CAPTCHA.