一个有关字符串子串的有趣问题

2016-08-04 22:51:00

问题描述：

输入一个字符串。
输入的字符串仅由'0'和'1'组成，比如'10100011101'这样的。
从输入的字符串中截取一段连续的片段作为子串，且子串满足从左往右数，'0'的个数总是不比'1'少。
输出其满足条件的最长的子串的长度。

下面是JavaScript的实现：

function subString(str){
    var arr = str.split('');
    var result = 0;
    (function loop(i){
        if (result + i > arr.length){
            return result;
        } else if (arr[i] !== '0'){
            loop(i+1);
        } else {
            var l = 1;
            var subLength = 1;            
            (function subLoop(k){
                if(k === arr.length){
                    return result;
                } else if (l > 0 || arr[k] === '0'){
                    subLength++;
                    l += arr[k]==='0' ? 1 : -1;
                    result = result>subLength ? result : subLength;
                    subLoop(k+1);
                } else {
                    loop(i+1)
                }
            }(i+1))
        }
    }(0))
}

解决思路：穷举从第i个字符开始的所有满足条件的最长字符串，取其中最长的。

关键字：JavaScript, 算法, result, arr

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击举报进行投诉反馈！