Curry_warrior
2020-03-16 14:34
采纳率: 55.2%
浏览 281
已采纳

Java中递归问题的base case

下面是一个递归问题的描述,我想了很久不知道怎么表达递归的base case。
图片说明

我的想法是如果最后字符串的长度跟字符串中不同字母出现的个数相等(比如abc字母出现个数为3,bcaa还是3),那就是base case。但是题目不让用for循环和正则表达式。
请教下该题的base case 是什么

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • 张一毛 2020-03-16 15:40
    已采纳

    字符串处理中使用递归,将字符串切割成一个字符+子字符串,然后递归处理子字符串。base case当然是子字符串是一个字符了,就不用执行了。

    public static String test3(String string) {
            if(string.length()<=1) {
                return string;
            }
            String s = string.substring(0,1);
            String end = string.substring(1, string.length());
            if(end.startsWith(s)) {
                return test3(end);
            }else {
                return s+test3(end);
            }
        }
    
    已采纳该答案
    打赏 评论
  • greadworld 2020-03-16 16:11

    public static void main(String[] args) {
    duplicateRemoval();
    useSetDuplicateRemoval();
    }

    //第一反应是用set去重
    public static void useSetDuplicateRemoval(){
        String a = "sdfasfasdfasdfsd";
        char[] chars = a.toCharArray();
        char[] resultChars = new char[chars.length];
        //为了有序所以选LinkedHashSet
        Set<String> result = buildString(chars, 0, new LinkedHashSet<>());
        System.out.println(result);
    }
    //递归向集合添加元素
    public static Set<String> buildString(char[] chars, int a, Set<String> s) {
        if (chars.length > a) {
            s.add(String.valueOf(chars[a]));
            buildString(chars, ++a, s);
        }
        return s;
    }
    
    //纯递归
    public static void duplicateRemoval(){
        String a = "sdfasfasdfas1dfsd";
        char[] chars = a.toCharArray();
        char[] resultChars = new char[chars.length];
        resultChars = buildString(chars, 0, resultChars, 0);
        System.out.println(resultChars);
    }
    //向新数组中添加元素
    public static char[] buildString(char[] charsOld, int i, char[] chars, int index) {
        if (chars.length > i) {
            if(0 == matches(chars, charsOld[i], 0)){
                chars[index] = charsOld[i];
                index++;
            }
            buildString(charsOld, ++i, chars, index);
        }
        return chars;
    }
    //判断数组是否含有该字符
    public static int matches(char[] chars, char c, int i){
        if (chars.length > i) {
            if(chars[i]==c){
                return 1;
            }
            return matches(chars, c, ++i);
        }
        return 0;
    }
    
    打赏 评论

相关推荐 更多相似问题