amaier amaier - 2 months ago 11
Java Question

Counting substrings recursively

I am struggling with an recursion problem that I do not know how to solve. Could you give a hint?

Example:
Given a string and a non-empty substring sub, compute recursively the number of times that sub appears in the string, without the sub strings overlapping.

strCount("catcowcat", "cat") → 2
strCount("catcowcat", "cow") → 1
strCount("catcowcat", "dog") → 0


This is the given method

public int strCount(String str, String sub) {
//...
}





Edit (from comment) what i've tried :

public int strCount(String str, String sub) {
if(str == null || str.length() == 0 || str.indexOf(sub) == -1)
return 0;

if(str.indexOf(sub) != )
str = str.replace(sub,"");

return 1+strCount(str,sub);
}

Answer Source

The way is pretty easy :

  • if the substring is contained into the String, remove it once, and say you find it once (return 1 + maybeThereIsMore)

  • else, say you did not find it and return 0;


public static int strCount(String str, String sub) {
    if (str.contains(sub)) {
        return 1 + strCount(str.replaceFirst(sub, ""), sub);
    }
    return 0;
}

strCount("catcowcat", "cat") → 1+strCount("cowcat", "cat") → 1+1+strCount("cow", "cat") → 2
strCount("catcowcat", "cow") → 1+strCount("catcat", "cow") → 1
strCount("catcowcat", "dog") → 0

Note : the method can be static, can it doesn't need any object, only the parameters