时间戳

首页 > 解决方案 > 计算字符串最大可能长度的算法

javascript - 计算字符串最大可能长度的算法

问题描述

问题：

给定一个字符串数组 arr。字符串 s 是具有唯一字符的 arr 子序列的串联。

返回 s 的最大可能长度

例子：

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

我的解决方案：

var maxLength = function(arr) {
    if(!arr || arr.length === 0)    return 0;
    
    let word = "";
    arr.sort((a,b) => b.length - a.length);
    let set = new Set();
    
    const removeFromSet = (str) => {
        for(let i=0; i<str.length; i++) {
            set.delete(str[i]);
        }
    }
    
    const isInSet = (str) => {
        for(let i=0; i<str.length; i++) {
            if(set.has(str[i])) {
                removeFromSet(str.substring(0, i));
                return true;
            }
            else 
                set.add(str[i]);
        }
        return false
    }
    
    for(let i=0; i<arr.length; i++) {
        if(!isInSet(arr[i])) {
            word += arr[i];
        }
    }
    
    return word.length;
};

输入失败：["ab","cd","cde","cdef","efg","fgh","abxyz"] 它应该返回 11，但我的解决方案返回 9。

我知道我的解决方案正在计算：“abxyzcdef”，它应该是：“abxyzfghcde”。有谁知道我做错了什么？

谢谢

标签： javascriptarraysstringset

解决方案

孔算法是递归的，仅从字符串数组开始。如果未定义第二个参数 str ，则将其设置为空字符串（仅在开始时）。
如果存在已构建的字符串，则遍历字符串数组查找。如果是这样，则将新的测试字符串拆分为 chars 并查看是否存在至少一个包含在构建字符串中的char （带有Array#some ）。如果这个条件也成立，那么字符串就不会包含唯一字符，所以我们可以继续。否则，到目前为止，这是一个可能的解决方案。
现在取出数组并删除所有已尝试过的测试字符串（包括实际测试过的），因为用它们进行测试没有用。用缩短的字符串数组递归调用算法本身，用实际的测试字符串扩展字符串。
查看实际测试字符串的长度加上递归调用的返回值是否大于最大值而不是实际化它。
遍历数组中的所有测试字符串后，返回允许字符串的最大长度。

扩展：我在开始时使用 Array.filter 检查所有字符串是否有多个相同字符的单词，因此不会测试“abba”。

function maxLength(array, str) {
       if (str === undefined) {
           str = '';
           array = array.filter(elem => elem.split('').every((char, key) => !(elem.slice(key+1)).includes(char)));
    };
    array = array.filter(elem => elem.split('').every((char, key) => !(elem.slice(key+1)).includes(char)));
    let max=0;
    for (let i=0; i<array.length; i++) {
        let test= array[i];
        if (str.length && test.split('').some(char => str.includes(char))) {
             continue;
        } else {
            let len = test.length + maxLength(array.slice(i), str + test);
            if (len>max) max=len;
        }
    }
    return max;
}

console.log( maxLength(["un","iq","ue"]) );
console.log( maxLength(["cha","r","act","ers"]) );
console.log( maxLength(["ab","cd","cde","cdef","efg","fgh","abxyz"]) );
console.log( maxLength(["yy","bkhwmpbiisbldzknpm"]) );

推荐阅读