有效的 0 和 1 字符串递归

Question

我想编写一个递归算法来评估一串 1 和 0 并确定该字符串是否有效。如果字符串连续包含 3 个零，则该字符串无效。

例如：

1010010001 无效

1111101101 有效

1000111101 无效

我不知道这个算法怎么写。感谢您的任何帮助。

Answer 1

你可以这样做（假设 str 是你的字符串，n 是它的长度，索引是基于 0 的）

           func ( index )
               if index >= n
                  return true 
               if index < 2
                  return func(index+1)
               if str[index] is 0 and str[index-1] is 0 and str[index-2] is 0
                  return false
               return func(index+1)

             // call func(0) , assuming str is global , also answer is boolean
             answer = func(0)

时间复杂度为 O(n)。只是为了这样一个直截了当的完整性我会用循环迭代地写它。

        //This is in c/c++
        bool answer = true;
        for(i = 2;i < n;i++)
        {
            if(str[i] == '0' && str[i-1] == '0' && str[i-2] == '0')
                  answer = false;
        }

Answer 2

public static boolean isValid(String s){
        return isValidInt(s)==3;
    }

    private static int isValidInt(String s){
        if( s == null || s.length() ==0)
                return 0;
        int prevSum=isValidInt(s.substring(1));
        if( prevSum == 3 )
            return 3;
        return s.charAt(0) != '0' ?0:1+prevSum;
    }

有效的 0 和 1 字符串递归

valid 0 and 1 String recursion

algorithm

recursion

data-structures