Dãy con (Subsequence)
Dãy con là dãy có thể dẫn xuất từ dãy khác bằng cách xóa một số ký tự mà không thay đổi thứ tự phần tử còn lại. Chuỗi bất kỳ là dãy con của chính nó, chuỗi rỗng là dãy con của mọi chuỗi.
Vấn đề
Cần viết hàm JS nhận mảng chuỗi, tìm độ dài dãy con không phổ biến (uncommon subsequence) dài nhất trong chúng. Dãy con không phổ biến là dãy con của một chuỗi trong mảng mà không phải là dãy con của bất kỳ chuỗi nào khác trong mảng. Nếu không tồn tại, trả về -1.
Ví dụ:
const arr = ["aba", "cdc", "eae"];
Kết quả:
const output = 3;
Giải thích kết quả:
"aba", "cdc", "eae" đều là dãy con không phổ biến độ dài 3.
Ví dụ
Mã thực hiện:
const arr = ["aba", "cdc", "eae"]; const longestUncommon = (strs) => { const map = {}; const arr = []; let max = -1; let index = -1; for(let i = 0; i < strs.length; i++){ map[strs[i]] = (map[strs[i]] || 0) + 1; if(map[strs[i]] > 1){ if(max < strs[i].length){ max = strs[i].length index = i; } } } if(index === -1) { strs.forEach(el =>{ if(el.length > max) max = el.length; }) return max; } for(let i = 0; i < strs.length; i++){ if(map[strs[i]] === 1) arr.push(strs[i]); } max = -1 for(let i = arr.length - 1; i >= 0; i--){ let l = arr[i]; let d = 0; for(let j = 0; j < strs[index].length; j++){ if(strs[index][j] === l[d]){ d++; } } if(d === l.length){ let temp = arr[i]; arr[i] = arr[arr.length - 1]; arr[arr.length - 1] = temp; arr.pop(); } } arr.forEach(el =>{ if(el.length > max) max = el.length; }) return max; }; console.log(longestUncommon(arr));
Kết quả
Kết quả in ra console:
3