Chuỗi từ
Giả sử word1 là tiền thân của word2 nếu và chỉ khi chúng ta có thể thêm chính xác một chữ cái vào bất kỳ đâu trong word1 để làm cho nó bằng với word2. Ví dụ:"abc" là tiền thân của "abac".
Chuỗi từ là một chuỗi các từ [word_1, word_2, ..., word_k] với k> =1, trong đó word_1 là tiền thân của từ_2, từ_2 là tiền nhiệm của từ_3, v.v.
Vấn đề
Chúng tôi bắt buộc phải viết một hàm JavaScript lấy một mảng chuỗi, arr, làm đối số đầu tiên và duy nhất.
Mỗi chuỗi trong mảng arr bao gồm các chữ cái viết thường tiếng Anh. Hàm của chúng ta sẽ trả về độ dài dài nhất có thể của một chuỗi từ với các từ được chọn từ mảng đã cho, arr.
Ví dụ:nếu đầu vào của hàm là -
const arr = ["a","b","ba","bca","bda","bdca"];
Sau đó, kết quả đầu ra phải là -
const output = 4;
Giải thích đầu ra:
Một trong những chuỗi từ dài nhất là "a", "ba", "bda", "bdca".
Ví dụ
Mã cho điều này sẽ là -
const arr = ["a","b","ba","bca","bda","bdca"];
const longestStrChain = (arr) => {
arr.sort((a, b) => a.length - b.length);
const isPredecessor = (word1 = '', word2 = '') => {
if(Math.abs(word1.length - word2.length) !== 1){
return false;
};
for(let i = 0; i < word2.length; i++){
const word = word2.slice(0, i) + word2.slice(i + 1);
if(word === word1){
return true;
};
};
return false;
};
const array = [];
let max = 0;
for(let i = arr.length - 1; i >= 0; i--){
array[i] = 1;
for(let j = arr.length - 1; j > i; j--){
if(isPredecessor(arr[i], arr[j])){
array[i] = Math.max(
array[i],
1 + array[j],
);
};
};
max = Math.max(max, array[i]);
};
return max;
};
console.log(longestStrChain(arr)); Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
4