Problem:
Given a string and a non-empty substring sub, compute recursively if at least n copies of sub appear in the string somewhere, possibly with overlapping. N will be non-negative.
strCopies("catcowcat", "cat", 2) → true
strCopies("catcowcat", "cow", 2) → false
strCopies("catcowcat", "cow", 1) → true
Solution:
public boolean strCopies(String str, String sub, int n) {
if (func(str, sub) == n) return true;
else return false;
}
private int func(String str, String sub) {
int strlen = str.length();
int sublen = sub.length();
if (strlen < sublen) return 0;
if (str.substring(0, sublen).equals(sub))
return 1 + func(str.substring(1), sub);
else
return func(str.substring(1), sub);
}
public boolean strCopies(String str, String sub, int n) {
ReplyDeleteif(n == 0)
return true;
if(str.length() < sub.length())
return false;
if(str.substring(0,sub.length()).equals(sub))
return strCopies(str.substring(1), sub, n-1);
return strCopies(str.substring(1), sub, n);
}
Above soln is not correct, as if called with n=0 then it will fail. Eg: strCopies("iiijjj", "ii", 0)
DeleteBetter solution is:
public boolean strCopies(String str, String sub, int n) {
if (str.length()<sub.length()) {
if (n == 0)
return true;
else
return false;
}
else if (str.substring(0, sub.length() ).equals(sub))
return strCopies(str.substring(1), sub, --n);
return strCopies(str.substring(1), sub, n);
}
public boolean strCopies(String str, String sub, int n) {
ReplyDeleteif(str.indexOf(sub)==-1 && n==0) return true;
if(str.indexOf(sub)!=-1)
{
return strCopies(str.substring(str.indexOf(sub)+1), sub, n-1);
}
return false;
}
I came up with this code..
ReplyDeleteint count;
public boolean strCopies(String str, String sub, int n) {
if (str.indexOf(sub) != -1) {
count++;
strCopies(str.substring(str.indexOf(sub)+1), sub, n);
}
if (count == n) {
return true;
}
else {
count = 0;
return false;
}
}
However it does not work with the case
strCopies("iiijjj", "i", 3)
Although in eclipse it returns true in coding bat the return value is false..Any ideas?
Fixed it:
Deleteboolean match;
public boolean strCopies(String str, String sub, int n) {
if (n == 0) {
match = true;
}
if (str.indexOf(sub) != -1) {
match = false;
n--;
strCopies(str.substring(str.indexOf(sub)+1), sub, n);
}
return match;
}
public boolean strCopies(String str, String sub, int n) {
ReplyDeleteif(n==0&&str.equals("")){
return true;
}
else if(str.indexOf(sub)==0){
return strCopies(str.substring(1),sub,n-1);
}
else if(str.indexOf(sub)!=0&& !str.equals("")){
return strCopies(str.substring(1),sub,n);
}
else{
return false;
}
/*Sometiems you need more trial and error. What helped was
*figuring out which arguement(s) were important so that I
*could make a proper base case.
*/
}
public boolean strCopies(String str, String sub, int n) {
ReplyDeleteint idx = str.indexOf(sub);
if (n==0 && idx==-1)
return true;
if (n>0 && idx==-1)
return false;
if (n==0 && idx>=0)
return false;
return strCopies((str.substring(0, idx) + str.substring(idx+1)), sub, --n);
}
public boolean strCopies(String str, String sub, int n) {
ReplyDeletereturn (str.indexOf(sub) == -1 && n == 0)
|| str.indexOf(sub) != -1
&& strCopies(str.substring(str.indexOf(sub) + 1), sub, n - 1);
}
public boolean strCopies(String str, String sub, int n) {
ReplyDeletereturn (!str.contains(sub) && n == 0)
|| str.contains(sub)
&& strCopies(str.substring(str.indexOf(sub) + 1), sub, n - 1);
}
public boolean strCopies(String str, String sub, int n) {
ReplyDeleteif(str.length() < sub.length()) return n == 0;
return str.startsWith(sub) ?
strCopies(str.substring(1), sub, n - 1) :
strCopies(str.substring(1), sub, n);
}