如何递归计算字符串中某些特定字符的数量？

Question

我在练习递归问题。有一些类型的问题要求您计算没有循环的String中特定字符的数量。

我应该使用什么样的方法？任何人都可以向我解释？

下面是一个问题：“给定一个字符串，递归计算（无循环）字符串中小写'x'字符的数量。

我的代码：

public int countX(String str) { 
    if(str.length()==0){ 
     return 0; 
    } 
    if(str.charAt(0)=='x'){ 
     return 1+ countX(str.substring(1)); 
    } 
    return countX(str); 
} 

Answer 1

就快，但你需要修改的情况下在str的第一个字母是不是'x'。您目前正在做的操作将导致无限递归，因为在str.charAt(0) != 'x'的情况下，您递归地调用str上的countX。然而，str仍然是第一个字母没有'x'的字符串，所以它会一次又一次地在str上调用countX等。所以解决方法是在str.substring(1)的第一个字母时仅调用countX是不是'x'像这样，

public int countX(String str) { 
    if(str.length()==0){ 
     return 0; 
    } 
    if(str.charAt(0)=='x'){ 
     return 1 + countX(str.substring(1)); 
    } 
    else{ 
     return countX(str.substring(1)); 
    } 
} 

你的方法之前

做比方说，我在"Hello"叫countX，这里的调用堆栈跟踪会是什么样子，

call countX("Hello") 
"Hello".length() != 0 so we move on to the next condition 
"Hello".charAt(0) != 'x' so we call countX("Hello") 
    call countX("Hello") 
    "Hello".length() != 0 so we move on to the next condition 
    "Hello".charAt(0) != 'x' so we call countX("Hello") 
     call countX("Hello") 
     "Hello".length() != 0 so we move on to the next condition 
     "Hello".charAt(0) != 'x' so we call countX("Hello"); 
      . 
      . 
      . 
      infinite recursion 

新的解决方案能做什么

call countX("Hello") 
"Hello".length() != 0 so we move on to the next condition 
"Hello".charAt(0) != 'x' so we call countX("ello") 
    call countX("ello") 
    "ello".length() != 0 so we move on to the next condition 
    "ello".charAt(0) != 'x' so we call countX("llo") 
     call countX("llo") 
     "llo".length() != 0 so we move on to the next condition 
     "llo".charAt(0) != 'x' so we call countX("lo"); 
      call countX("lo") 
      "lo".length() != 0 so we move on to the next condition 
      "lo".charAt(0) != 'x' so we call countX("o"); 
       call countX("o") 
       "o".length() != 0 so we move on to the next condition 
       "o".charAt(0) != 'x' so we call countX(""); 
        call countX("") 
        "".length() == 0 so return 0 
       return 0 
      return 0 
     return 0 
    return 0 
return 0 

请注意，在该解决方案中，我们总能有基本案例（str.length()==0）的一种方式。而之前会有一些情况（当我们遇到不是x的字母时）会阻止该方法到达基本情况。

Answer 2

我应该使用什么样的方法？任何人都可以向我解释？

一个解决方案是使用一个StringBuilder，只是在方法的每次调用删除第一个字符，最终，你会得到基本情况和应该输出正确的结果。

public int countX(String str) { 
     if(str.length() == 0) return 0; 

     StringBuilder builder = new StringBuilder(str); 
     if(str.charAt(0) == 'x'){ 
      builder.deleteCharAt(0); 
      return 1 + counter(builder.toString()); 
     } 

     builder.deleteCharAt(0); 
     return counter(builder.toString()); 
} 

但是，如果你想与您当前的解决方案来进行，你需要替换此：

return countX(str); 

与此：

return countX(str.substring(1)); 

的问题是，如果当前字符不是'x'，您只是忽略它，并未将问题简化为基本情况。

Answer 3

我了解您的需求。在下面，你有你需要递归计算字符串中的字符的方法。

static int countCharRecursively(String str, char ch){ 

    if(str.indexOf(ch) != -1) 
    {   
     return countCharRecursively(str.substring(0, str.indexOf(ch)), ch)+ 
      countCharRecursively(str.substring(str.indexOf(ch)+1),ch) + 1; 
    } 
    else{ 
     return 0; 
    } 
} 

这是一个可以运行的完整程序。

public class CountCharRecursivelyInString{ 

public static void main(String[] args){ 

    String str = "hello the world"; 

    char ch = 'l'; 

    int nbr = countCharRecursively(str, ch); 

    System.out.println(ch + " : " + nbr); 
} 

static int countCharRecursively(String str, char ch){ 

    if(str.indexOf(ch) != -1) 
    {   
     return countCharRecursively(str.substring(0, str.indexOf(ch)), ch)+ 
      countCharRecursively(str.substring(str.indexOf(ch)+1),ch) + 1; 
    } 
    else{ 
     return 0; 
    } 
} 
}