2019大厂面试题，据说90%的人当场没写对，30%写出思路得了部分分数

Question

需要在字符串y中寻找：含有字符串x所有字符的最短字符串说明：
如果 y 中不存这样的最短字符串，则返回空字符串 ""。
如果 y 中存在这样的最短字符串，返回任意一个最短匹配。例子：
输入: y = "dhs5goe13j45ddsfoea", x = "esd"
输出: "dsfoe"

Answer 1

最终的输出 "dsfoe" 包含了X的"e","s","d"所有字母，所以"dsfoe"做为输出是对的，同时"dsfoe"是y里面包含X最短的。比如"dhs5goe"也包含了X的"e","s","d"所有字母，但它不是最短的

Answer 2

var y = "dhs5goe13j45ddsfoea", x = "esd";
var str = "";
var arr = y.match(new RegExp("[^"+x+"]*["+x+"]","g"));
for (var i = 0; i < arr.length; i++) {
var r = arr[i].slice(-1);
var set = new Set();
set.add(r);
for (var j = i+1; j < arr.length; j++) {
r += arr[j];
set.add(arr[j].slice(-1));
if (set.size==x.length) {
if (str=="" || r.length<str.length)
str = r;
break;
}
}
}
alert(str);

Answer 3

var y = "a", x = "b";//抛错 Uncaught TypeError: Cannot read property 'length' of null

Answer 4

var arr = y.match(new RegExp("[^"+x+"]*["+x+"]","g"))||[];

Answer 5

var arr = y.match(new RegExp("[^"+x+"]*["+x+"]","g"))||[];

var y = "a", x = "a";
输出应该是a，而不是""

Answer 6

var y = "a", x = "a";
var str = "";
var arr = y.match(new RegExp("[^"+x+"]*["+x+"]","g"))||[];
for (var i = 0; i < arr.length; i++) {
var r = "";
var set = new Set();
for (var j = i; j < arr.length; j++) {
r += j==i? arr[j].slice(-1) : arr[j];
set.add(arr[j].slice(-1));
if (set.size==x.length) {
if (str=="" || r.length<str.length)
str = r;
break;
}
}
}
alert(str);

Answer 7

var y = "aa", x = "aa";
输出应该是aa，而不是""

Answer 8

    function test(y, x) {
        var pos = {}, temp = [], min = { start: 0, end: 0, len: y.length };
        //去重复字符，转对象
        x.split('').forEach(function (s) { pos[s] = [] });
        //获取各个匹配字符的位置
        for (var k in pos) {
            var index = y.indexOf(k, 0);
            //如果某个字符不能匹配则提示并退出
            if (index == -1) {
                alert('不能匹配字符' + k);
                return '';
            }
            while (index > -1) {
                pos[k].push(index);
                index = y.indexOf(k, index + 1);
            }
        }
        //生成组合
        for (var k in pos) {
            if (temp.length == 0) {
                pos[k].forEach(function (n) { temp.push([n]); });
            } else {
                var temp2 = [];
                temp.forEach(function (arr) {
                    pos[k].forEach(function (n) {
                        temp2.push(arr.concat([n]));
                    });
                });
                temp = temp2;
            }
        }
        //计算最小长度字符串
        temp.forEach(function (arr) {
            arr.sort(function (a, b) { return a - b });
            var _ = { start: arr[0], end: arr[arr.length - 1], len: arr[arr.length - 1] - arr[0] };
            if (_.len < min.len) {
                min = _;
            }
        });
        return y.substring(min.start, min.end + 1);
    }
    var result = test('dhs5goe13j45ddsfoea', 'esdssddddeee');
    alert(result);

Answer 9

var y = "a", x = "aa";
输出应该是""，而不是"a"

Answer 10

既然是把x拆开来一个一个判断，为什么aa不能匹配为a呢？a明显比aa要短

Answer 11

var y = "aa", x = "aa";
var str = "";
var rx = x.replace(/([\\\/\(\)\[\]\{\}\"\'\?\+\-\*\|\^\$\.])/g,"\\$1");
var arr = y.match(new RegExp(".*?["+rx+"]","g"))||[];
for (var i = 0; i < arr.length; i++) {
var r = "";
var t = x;
for (var j = i; j < arr.length; j++) {
r += j==i? arr[j].slice(-1) : arr[j];
t = t.replace(arr[j].slice(-1),"");
if (t.length==0) {
if (str=="" || r.length<str.length)
str = r;
break;
}
}
}
alert(str);

Answer 12

做对了，就是性能不太理想，下面例子如果能控制在800毫秒间，就是完美var y = "obzcopzocynyrsgsarijyxnkpnukkrvzuwdjldxndmnvevpgmxrmvfwkutwekrffnloyqnntbdohyfqndhzyoykiripdzwiojyoznbtogjyfpouuxvumtewmmnqnkadvzrvouqfbbdiqremqzgevkbhyoznacqwbhtrcjwfkzpdstpjswnpiqxjhywjanhdwavajrhwtwzlrqwmombxcaijzevbtcfsdcuovckoalcseaesmhrrizcjgxkbartdtotpsefsrjmvksqyahpijsrppdqpvmuocofuunonybjivbjviyftsyiicbzxnwnrmvlgkzticetyfcvqcbjvbufdxgcmesdqnowzpshuwcseenwjqhgsdlxatamysrohfnixfprdsljyyfhrnnjsagtuihuczilgvtfcjwgdhpbixlzmakebszxbhrdibpoxiwztshwczamwnninzmqrmpsviydkptjzpktksrortapgpxwojofxeasoyvyprjoguhqobehugwdvtzlenrcttuitsiijswpogicjolfxhiscjggzzissfcnxnvgftxvbfzkukqrtalvktdjsodmtgzqtuyaqvvrbuexgwqzwduixzrpnvegddyyywaquxjxrnuzlmyipuqotkghfkpknqinoidifnfyczzonxydtqroazxhjnrxfbmtlqcsfhshjrxwqvblovaouxwempdrrplefnxmwrwfjtebrfnfanvvmtbzjesctdgbsfnpxlwihalyiafincfcwgdfkvhebphtxukwgjgplrntsuchyjjuqozakiglangxkttsczhnswjksnuqwflmumpexxrznzwxurrysaokwxxqkrggytvsgkyfjrewrcvntomnoazmzycjrjrqemimyhriyxgrzcfuqtjhvjtuhwfzhwpljzajitrhryaqchnuawbxhxrpvyqcvhpggrpplhychyulijhkglinibedauhvdydkqszdbzfkzbvhldstocgydnbfjkcnkfxcyyfbzmmyojgzmasccaahpdnzproaxnexnkamwmkmwslksfpwirexxtymkmojztgmfhydvlqtddewjvsrmyqjrpycbmndhupmdqqabiuelacuvxnhxgtpvrtwfgzpcrbhhtikbcqpctlxszgpfbgcsbaaiapmtsucocmpecgixshrrnhyrpalralbccnxvjzjllarqhznzghswqsnfuyywmzbopyjyauknxddgdthlabjqtwxpxwljvoxkpjjpfvccyikbbrpdsyvlxscuoofkecwtnfkvcnzbxkeabtdusyhrqklhaqreupakxkfzxgawqfwsaboszvlshwzhosojjotgyagygguzntrouhiweuomqptfjjqsxlbylhwtpssdlltgubczxslqjgxuqnmpynnlwjgmebrpokxjnbiltvbebyytnnjlcwyzignmhedwqbfdepqakrelrdfesqrumptwwgifmmbepiktxavhuavlfaqxqhreznbvvlakzeoomykkzftthoemqwliednfsqcnbexbimrvkdhllcesrlhhjsspvfupxwdybablotibypmjutclgjurbmhztboqatrdwsomnxnmocvixxvfiqwmednahdqhxjkvcyhpxxdmzzuyyqdjibvmfkmonfxmohhshpkhmntnoplphqyprveyfsmsxjfosmicdsjrieeytpnbhlsziwxnpmgoxneqbnufhfwrjbqcsdfarybzwaplmxckkgclvwqdbpumsmqkswmjwnkuqbicykoisqwoootrdpdvcuiuswfqmrkctsgrevcxnyncmivsxbpbxzxpwchiwtkroqisnmrbmefbmatmdknaklpgpyqlsccgunaibsloyqpnsibwuowebomrmcegejozypjzjunjmeygozcjqbnrpakdermjcckartbcppmbtkhkmmtcngteigjnxxyzaibtdcwutkvpwezisskfaeljmxyjwykwglqlnofhycwuivdbnpintuyhtyqpwaoelgpbuwiuyeqhbvkqlsfgmeoheexbhnhutxvnvfjwlzfmvpcghiowocdsjcvqrdmkcizxnivbianfpsnzabxqecinhgfyjrjlbikrrgsbgfgyxtzzwwpayapfgueroncpxogouyrdgzdfucfrywtywjeefkvtzxlwmrniselyeodysirqflpduvibfdvedgcrzpzrunpadvawfsmmddqzaaahfxlifobffbyzqqbtlcpquedzjvykvarayfldvmkapjcfzfbmhscdwhciecsbdledspgpdtsteuafzbrjuvmsfrajtulwirzagiqjdiehefmfifocadxfuxrpsemavncdxuoaetjkavqicgndjkkfhbvbhjdcygfwcwyhpirrfjziqonbyxhibelinpllxsjzoiifscwzlyjdmwhnuovvugfhvquuleuzmehggdfubpzolgbhwyeqekzccuypaspozwuhbzbdqdtejuniuuyagackubauvriwneeqfhtwkocuipcelcfrcjcymcuktegiikyosumeioatfcxrheklookaqekljtvtdwhxsteajevpjviqzudnjnqbucnfvkybggaybebljwcstmktgnipdyrxbgewqczzkaxmeazpzbjsntltjwlmuclxirwytvxgvxscztryubtjweehapvxrguzzsatozzjytnamfyiitreyxmanhzeqwgpoikcjlokebksgkaqetverjegqgkicsyqcktmwjwakivtsxjwrgakphqincqrxqhzbcnxljzwturmsaklhnvyungjrxaonjqomdnxpnvihmwzphkyuhwqwdboabepmwgyatyrgtboiypxfavbjtrgwswyvcqhzwibpisydtmltbkydhznbsvxktyfxopwkxzbftzknnwipghuoijrbgqnzovxckvojvsqqraffwowfvqvfcmiicwitrhxdeombgesxexedlakitfovtydxunqnwqqdeeekiwjnwoshqcsljiicgobbbuqakjdonjawgjlezdnqhfdqnmsuavxdpnfzwipmspiabveaarshzwxmirgkmfncvtdrdvfxkpxlkdokxgtwcskmjryyymcthfnkasinihaunohkxaibtsqelockaefjmsuolebtnepauwmrxutspjwaxbmahsjtkfkxlnszribmeofbkyvbjscjtqjakuwvcgunvnonvqbbggfshauqsyznokqbhowjusypfnecffenojfvlblgzntqzlrgzprvhqnpfrrkzxznieiuivajivzijsqijigtatifmbplzqahuidegfoobpymkputzamzvweiyvvzlwihgmmmrcburbgbsdxrfjsbiylitghgcpqjbevvgypxcybubyoijijrhuzcdijfybqbfowlookqmlnplbxvjjosfqviygqyhgamuwzjklbyzopkrnhbywtfoqomweldmlrhjqswctubiknzzvcztyehouvnyiqnvkufaobehxhrjvtisxjlxoumipzjarwvbsaegdkpbsjmpevjbewzuqnfhoohhmdjgfpmjzdmtmykqvtucptwfidpwtwffzolffzqfdearclkyeecuzabjeqhxpmfodsvisnpxrqowdawheydfyhoexvcmihdlzavtqlshdhdgjzpozvvackebhgqppvcrvymljfvooauxcjnbejdivikcoaugxwzsulgfqdtefpehbrlhaoqxwcancuvbqutnfbuygoemditeagmcveatgaikwflozgdhkyfqmjcruyyuemwbqwxyyfiwnvlmbovlmccaoguieu"
var x = "cjgamyzjwxrgwedhsexosmswogckohesskteksqgrjonnrwhywxqkqmywqjlxnfrayykqotkzhxmbwvzstrcjfchvluvbaobymlrcgbbqaprwlsqglsrqvynitklvzmvlamqipryqjpmwhdcsxtkutyfoiqljfhxftnnjgmbpdplnuphuksoestuckgopnlwiyltezuwdmhsgzzajtrpnkkswsglhrjprxlvwftbtdtacvclotdcepuahcootzfkwqhtydwrgqrilwvbpadvpzwybmowluikmsfkvbebrxletigjjlealczoqnnejvowptikumnokysfjyoskvsxztnqhcwsamopfzablnrxokdxktrwqjvqfjimneenqvdxufahsshiemfofwlyiionrybfchuucxtyctixlpfrbngiltgtbwivujcyrwutwnuajcxwtfowuuefpnzqljnitpgkobfkqzkzdkwwpksjgzqvoplbzzjuqqgetlojnblslhpatjlzkbuathcuilqzdwfyhwkwxvpicgkxrxweaqevziriwhjzdqanmkljfatjifgaccefukavvsfrbqshhswtchfjkausgaukeapanswimbznstubmswqadckewemzbwdbogogcysfxhzreafwxxwczigwpuvqtathgkpkijqiqrzwugtr"
var timer1 = Date.now()
var str = "";
var rx = x.replace(/([\\\/\(\)\[\]\{\}\"\'\?\+\-\*\|\^\$\.])/g,"\\$1");
var arr = y.match(new RegExp(".*?["+rx+"]","g"))||[];
for (var i = 0; i < arr.length; i++) {
    var r = "";
    var t = x;
    for (var j = i; j < arr.length; j++) {
        r += j==i? arr[j].slice(-1) : arr[j];
        t = t.replace(arr[j].slice(-1),"");
        if (t.length==0) {
            if (str=="" || r.length<str.length)
                str = r;
            break;
        }
    }
}
console.log(str)
var timeDiff = Date.now() - timer1
console.log(timeDiff)

Answer 13

这个反向思维可能速度更优，对x去重，将y所有的字符替换成.然后记录位置string本身就是个数组单次遍历这点数据没有威胁，接着取x去重的长度，去匹配y中所有符合长度的串，拿到一个集合去对照位置，具体代码就不写了

Answer 14

<script>
console.log(new Date().getMilliseconds())
let x = 'esd',          //可写多个  个数越多执行越慢
xArr = x.split('');
xsArr = permute([],xArr);
console.log(xsArr)
let matchs = [],
    str = 'dhs5goe13j45ddsfoea';
xsArr.forEach(item => {
    let regexStr = createRegex(item,x.length);
    let regex = eval(regexStr),
        match = str.match(regex);
        console.log(regexStr)
        matchs = matchs.concat(match)
});
matchs = matchs.filter(x=>{
    console.log(x)
    return x!=null && x.length >0
})
matchs = matchs.sort((a,b)=>a.length-b.length)
console.log(matchs)
console.log(matchs[0])
console.log(new Date().getMilliseconds())/**
 * 根据提供的关键字符构建regex表达式
*/
function createRegex(item,len){
    let regex = '/'
    for(let i = 0;i<len -1;i++){
        regex +=`${item[i]}[^${item[i]}]*?`
    }
    regex += `${item[len-1]}/g`;
    return regex;
}/**
 * 对提供的关键字符排序组合（网上找的）
 * 
*/
function permute(temArr,testArr){
   var permuteArr=[];
   var arr = testArr;
   function innerPermute(temArr){
         for(var i=0,len=arr.length; i<len; i++) {
             if(temArr.length == len - 1) {
                 if(temArr.indexOf(arr[i]) < 0) {
                     permuteArr.push(temArr.concat(arr[i]));
                 }
                 continue;
             }
             if(temArr.indexOf(arr[i]) < 0) {
                 innerPermute(temArr.concat(arr[i]));
             }
         }
     }
 innerPermute(temArr);
 return permuteArr;     
}
</script>

Answer 15

var y = "a", x = "aa";
输出应该是""，而不是undefined

Answer 16

还是把代码敲出来比较有说服力点，以下链接时解题过程和代码。你要求800ms 实际执行了150ms 应该满足你的要求。
https://blog.csdn.net/a807719447/article/details/102902924

Answer 17

抱歉，没接触过java，无法验证

Answer 18

抱歉，没接触过java，无法验证
回头给你贴个js版本吧 还有 那个 x="aa" y=“a”这个输出  a 才是正确得，符合题题意得。

Answer 19

抱歉，没接触过java，无法验证
回头给你贴个js版本吧 还有 那个 x="aa" y=“a”这个输出  a 才是正确得，符合题题意得。
他这个x="aa"的意思是匹配的子串中要包含两个a

Answer 20

抱歉，没接触过java，无法验证
回头给你贴个js版本吧 还有 那个 x="aa" y=“a”这个输出  a 才是正确得，符合题题意得。
他这个x="aa"的意思是匹配的子串中要包含两个a这没道理，如果题目有明确要求需要包含两个a那么需要，如果没有明确要求，那我包含了就可以了，一般这种题目如果有特别要求，会明确出来的

Answer 21

抱歉，没接触过java，无法验证
回头给你贴个js版本吧 还有 那个 x="aa" y=“a”这个输出  a 才是正确得，符合题题意得。
他这个x="aa"的意思是匹配的子串中要包含两个a举个例子数组升序排列如果包含两个1那，按这么理解题意我是不是需要理解成，下标小的排前面

Answer 22

y = "a" , x = "aa"输出就是""'aa'是两个字符a组成的，y只有一个字符a，并不包含