需要在字串y中尋找：含有字串x所有字符的最短字串
說明：
如果 y 中不存這樣的最短字串，則回傳空字串 ""。
如果 y 中存在這樣的最短字串，回傳任意一個最短匹配。
例子：
輸入: y = "dhs5goe13j45ddsfoea", x = "esd"
輸出: "dsfoe"
uj5u.com熱心網友回復：
根本看不懂 什么意思uj5u.com熱心網友回復：
最終的輸出 "dsfoe" 包含了X的"e","s","d"所有字母，所以"dsfoe"做為輸出是對的，同時"dsfoe"是y里面包含X最短的。比如"dhs5goe"也包含了X的"e","s","d"所有字母，但它不是最短的
uj5u.com熱心網友回復：
uj5u.com熱心網友回復：
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);
uj5u.com熱心網友回復：
var y = "a", x = "b";
//拋錯 Uncaught TypeError: Cannot read property 'length' of null
uj5u.com熱心網友回復：
var arr = y.match(new RegExp("[^"+x+"]*["+x+"]","g"))||[];
uj5u.com熱心網友回復：
var y = "a", x = "a";
輸出應該是a，而不是""
uj5u.com熱心網友回復：
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);
uj5u.com熱心網友回復：
var y = "aa", x = "aa";
輸出應該是aa，而不是""
uj5u.com熱心網友回復：
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);
uj5u.com熱心網友回復：
x中的字符可以重復的嗎？
uj5u.com熱心網友回復：
包含的字符應該是去除重復字符的，因為位置不要求，如果不去除重復字符怎么計算？uj5u.com熱心網友回復：
var y = "a", x = "aa";
輸出應該是""，而不是"a"
uj5u.com熱心網友回復：
題無禁止即自由，所以可以重復
uj5u.com熱心網友回復：
既然是把x拆開來一個一個判斷，為什么aa不能匹配為a呢？a明顯比aa要短uj5u.com熱心網友回復：
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);
uj5u.com熱心網友回復：
做對了，就是性能不太理想，下面例子如果能控制在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)
uj5u.com熱心網友回復：
這個反向思維可能速度更優，對x去重，將y所有的字符替換成.然后記錄位置string本身就是個陣列單次遍歷這點資料沒有威脅，接著取x去重的長度，去匹配y中所有符合長度的串，拿到一個集合去對照位置，具體代碼就不寫了uj5u.com熱心網友回復：
估算下來執行時間應該會在幾十毫秒吧uj5u.com熱心網友回復：
<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>
uj5u.com熱心網友回復：
簡單易懂，謝謝！（湊字數）
uj5u.com熱心網友回復：
var y = "a", x = "aa";
輸出應該是""，而不是undefined
uj5u.com熱心網友回復：
還是把代碼敲出來比較有說服力點，以下鏈接時解題程序和代碼。你要求800ms 實際執行了150ms 應該滿足你的要求。https://blog.csdn.net/a807719447/article/details/102902924
uj5u.com熱心網友回復：
抱歉，沒接觸過java，無法驗證
uj5u.com熱心網友回復：
回頭給你貼個js版本吧 還有 那個 x="aa" y=“a”這個輸出 a 才是正確得，符合題題意得。
uj5u.com熱心網友回復：
他這個x="aa"的意思是匹配的子串中要包含兩個a
uj5u.com熱心網友回復：
這沒道理，如果題目有明確要求需要包含兩個a那么需要，如果沒有明確要求，那我包含了就可以了，一般這種題目如果有特別要求，會明確出來的uj5u.com熱心網友回復：
舉個例子陣列升序排列如果包含兩個1那，按這么理解題意我是不是需要理解成，下標小的排前面uj5u.com熱心網友回復：
y = "a" , x = "aa"輸出就是""
'aa'是兩個字符a組成的，y只有一個字符a，并不包含
uj5u.com熱心網友回復：
題目的例子已經給了隱性條件是不重復的x了，不用糾結。uj5u.com熱心網友回復：
我看了一眼所想到的，應該還有更好的。每個字符索引存入相應字符索引陣列，然后直接比較索引相減相加最小的。uj5u.com熱心網友回復：
y = 'dhs5goe13j45ddsfoea'
x = 'esd'
seen = set(x)
for jj in range(len(y)):
seen.discard(y[jj])
if len(seen) == 0:
break
i = 0
count = {}
ans = y
for j in range(len(y)):
count.setdefault(y[j], 0)
count[y[j]] += 1
while count[y[i]] > 1 or y[i] not in x:
count[y[i]] -= 1
i += 1
if j >= jj and j - i < len(ans):
ans = y[i:j + 1]
print(ans)
O(n) 復雜度
17樓的樣例可以毫秒級出解
uj5u.com熱心網友回復：
Traceback (most recent call last):
File "C:/Users/Administrator/Desktop/aaa.py", line 15, in <module>
while count[y[i]] > 1 or y[i] not in x:
KeyError: 'b'
uj5u.com熱心網友回復：
y = 'dhs5goe13j45ddsfoea'
x = 'esd'
seen = set(x)
for jj in range(len(y)):
seen.discard(y[jj])
if len(seen) == 0:
break
else:
print("no answer")
i = 0
count = {}
ans = y
for j in range(len(y)):
count.setdefault(y[j], 0)
count[y[j]] += 1
while i <= j and (count[y[i]] > 1 or y[i] not in x):
count[y[i]] -= 1
i += 1
if j >= jj and j - i < len(ans):
ans = y[i:j + 1]
print(ans)
處理了越界情況
uj5u.com熱心網友回復：
let y = "dhs5goe13j45ddsfoea"
let x = "esd"
let matches = {};
for (let i of x) {
let rex = new RegExp(i, "g")
let match;
while (match = rex.exec(y)) {
matches[match.index] = i
}
}
let a = {}
let o = {}
let min = 999999999
let minstr
for (let i in matches) {
a[i] = []
o[i] = []
for (let b in a) {
if (a[b].length < x.length) {
if (a[b].indexOf(matches[i]) == -1) {
a[b].push(matches[i])
o[b].push(i)
}
}
if (a[b].length == x.length) {
if (o[b][x.length - 1] - o[b][0] < min) {
min = o[b][x.length - 1] - o[b][0]
minstr = y.substr(o[b][0], min + 1) + "，位于" + o[b][0] + "-" + o[b][x.length - 1]
}
}
}
}
alert(minstr)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/37179.html
標籤：JavaScript
上一篇：canvas 畫圖 格式錯誤