Найти самый длинный префикс, который также является суффиксом в строке - Javascript - PullRequest
Новая
       36

Найти самый длинный префикс, который также является суффиксом в строке - Javascript

0 голосов
/ 25 мая 2019

Ссылка на вызов codewars

Мне нужно вернуть длину самого длинного префикса, который также является суффиксом строки в Javascript.

Насколько я понимаю, префиксы в "abcd":

['a', 'ab', 'abc']

И суффиксы в "abcd":

[ 'bcd', 'cd', 'd' ]

Таким образом, длина самого длинного префикса, который также является суффиксом в "abcd", в этом случае равна 0, потому что нет префиксов, которые также являются суффиксами в "abcd".

До сих пор я мог выяснить, как получить суффиксы в массив для сравнения, но не префиксы. 

function returnLongestPrefixAndSuffix(string) {

  let prefixes = [];
  let suffixes = [];

  for (let i = 0; i < string.length -1; i++) {
    prefixes.push(string.slice(i));
  }

  for (let i = 1; i < string.length; i++) {
    suffixes.push(string.slice(i));
  }

  return prefixes + " " + suffixes;

}

console.log(returnLongestPrefixAndSuffix("abcd"));

Я не понимаю, как начинать с начала строки и добавлять каждый элемент в массив каждый раз на один символ, исключая элемент, который будет включать последний.

Пожалуйста, следуйте моей текущей логике, если это возможно.

РЕДАКТИРОВАТЬ : Мой код теперь выглядит так: 

function solve(string) {

    let prefixes = [];
    let suffixes = [];
    let includedList = [];

    for (let i = 1; i < string.length; i++) {
      prefixes.push(string.slice(0, i));
    }

    for (let i = 1; i < string.length; i++) {
      suffixes.push(string.slice(-i));
    }

    console.log(prefixes);
    console.log(suffixes);

    for (let i = 0; i < prefixes.length; i++) {
        let element = prefixes[i];
        if (suffixes.includes(element) === true) {
            includedList.push(element);
        }
    }

    console.log(includedList);
    if (includedList.length === 0) {
        return 0;
    }
    else {
        let overlap = prefixes.filter(value => suffixes.includes(value));
        console.log(overlap);
        let longest = includedList.sort(function (a, b) { return b.length - a.length; })[0];
        return longest.length;
    }
}

console.log(solve("abcdabc"));

И это проходит тест 10049, но не проходит 163 теста на кодовых войнах. Я до сих пор не знаю, что делать с переменной overlap или как исключить перекрытия из массива includedList.

Ответы [ 3 ]

2 голосов
/ 27 мая 2019 
function solve(string) {

    for (let i = Math.floor(string.length / 2); i > 0; i--) {

        let prefix = string.slice(0, i);
        let suffix = string.slice(-i);

        if (prefix == suffix) {
            return i;
        }
    }
    return 0;
}

console.log(solve("abcdabc"));

Чтобы учесть перекрытие, инициализируйте цикл for следующим образом:

let i = Math.floor(string.length / 2)

Это инициализирует цикл for в промежуточной точке вашей строки, так что вы можете отсчитывать и сравнивать, является ли префикс == суффиксом, начиная с самого длинного.

Вы можете вернуть prefix.length, но это будет то же самое, что и i.

Кроме того, обязательно return 0 за пределами цикла for. Потому что если вы попробуете: 

if (prefix != suffix) {
    return 0;
   }

внутри цикла for, он тут же перестанет считать.

1 голос
/ 25 мая 2019

Пожалуйста, смотрите документацию по функции slice, для этого может потребоваться второй аргумент: https://www.w3schools.com/jsref/jsref_slice_string.asp

Таким образом, следуя вашей логике, один из способов получения префиксов будет: 

for (let i = 1; i <= string.length; i++) {
  prefixes.push(string.slice(0, i));
}

EDIT: Ваш новый код не работает по двум причинам:

  1. Возможно, в итоге includedList окажется пустым, но вы все равно попытаетесь извлечь из него первый элемент.

  2. Вы не учитываете совпадения. Для ввода aaa правильный результат - a, поскольку префикс aa перекрывается с соответствующим суффиксом. Другими словами, результат не может быть длиннее половины длины ввода.

1 голос
/ 25 мая 2019

Чтобы получить префиксы, вы можете использовать второй аргумент .slice: 

  string.slice(0, i)

Обратите внимание, что для получения суффиксов вы также можете взять строку с конца: 

  string.slice(-i)

Нет смысла собирать префиксы и суффиксы в массивах, просто ищите самый большой i, где суффикс равен префиксу.

...