Самый длинный общий префикс в Javascript

avatar
Harsh Mishra
8 августа 2021 в 16:37
5121
12
5

Я пытаюсь решить задачу Leet Code 14. Самый длинный общий префикс:

Напишите функцию для поиска самой длинной строки общего префикса среди массива строк.

Если общего префикса нет, вернуть пустую строку "".

Пример 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Пример 2:

Input: strs = ["dog","racecar","car"]
Output: ""

Объяснение: Среди входных строк нет общего префикса.

Ограничения:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] состоит только из строчных букв латинского алфавита.

Мое решение:

let strs = ["flower", "flow", "flight"];

var longestCommonPrefix = function (strs) {
  for (let i = 0; i < strs.length; i++) {
    for (let j = 0; j < strs[i].length; j++) {
       // console.log(strs[i+2][j]);
      if (strs[i][j] == strs[i + 1][j] && strs[i + 1][j] ==strs[i + 2][j]) {
        return (strs[i][j]);
        
      } else {
        return "0";
      }
    }
  }
};

console.log(longestCommonPrefix(strs));

Вывод: f

Как я могу перебрать каждый символ и проверить, совпадают ли они, а затем перейти к следующему, и если это не удастся, будет возвращен самый длинный общий префикс?

Источник
Mike 'Pomax' Kamermans
8 августа 2021 в 16:41
1

Если вы не знаете, что не так: ваш первый план действий — выяснить, что не так. Возможно, после того, как вы это сделаете, вы не сможете понять, как это исправить, но вам нужно потратить время и усилия на отладку собственного кода: используйте небольшое число в качестве входных данных и поместите несколько журналов консоли. в ваших циклах, или даже лучше, но оператор debugger и используйте отладчик браузера для пошагового выполнения вашего кода, наблюдая за переменными. Когда вы знаете что должно происходить на каждой итерации, вы можете довольно быстро определить, что не так. Кроме того, в примечании JS: не используйте var x = function... , просто объявите функцию.

Harsh Mishra
8 августа 2021 в 16:55
0

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

Mike 'Pomax' Kamermans
8 августа 2021 в 17:25
0

Затем вы захотите обновить свой пост, чтобы объяснить, что вы нашли, где вы видите, что что-то идет не так, и что вы уже изучили, чтобы, надеюсь (но безуспешно), исправить ситуацию.

Ответы (12)

avatar
derpirscher
8 августа 2021 в 17:35
5

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

function prefix(words){
  // check border cases size 1 array and empty first word)
  if (!words[0] || words.length ==  1) return words[0] || "";
  let i = 0;
  // while all words have the same character at position i, increment i
  while(words[0][i] && words.every(w => w[i] === words[0][i]))
    i++;
  
  // prefix is the substring from the beginning to the last successfully checked i
  return words[0].substr(0, i);
}

console.log(1, prefix([]));
console.log(2, prefix([""]));
console.log(3, prefix(["abc"]));
console.log(4, prefix(["abcdefgh", "abcde", "abe"]));
console.log(5, prefix(["abc", "abc", "abc"]));
console.log(6, prefix(["abc", "abcde", "xyz"]));
Harsh Mishra
9 августа 2021 в 07:32
0

Большое вам спасибо за вашу помощь. Скажите, пожалуйста, какова временная сложность этого решения? Поскольку я также сделал то же самое, но с временной сложностью O (n2).

Harsh Mishra
9 августа 2021 в 07:32
0

let strs = ["flower", "flow", "floght"]; var longestCommonPrefix = function (strs) { for (let i = 0; i < strs.length; i++) { for (let j = 0; j < strs[i].length; j++) { while(strs[i][j] == strs[i + 1][j] && strs[i][j] == strs[i + 2][j]){ j++; } return String(strs).substr(0,j); } } } console.log(longestCommonPrefix(strs));

derpirscher
9 августа 2021 в 07:58
0

Сложность равна O(n * m), где n — количество слов в массиве, а m — длина префикса.

Harsh Mishra
9 августа 2021 в 13:21
0

И в первом утверждении if это похоже на Conditional (ternary) operator? Если возможно, не могли бы вы объяснить это или поделиться документацией, где я могу узнать об этом?

derpirscher
9 августа 2021 в 13:57
0

Нет, это не имеет ничего общего с тернарным оператором. В words[0] || "" это простой оператор ИЛИ ||. То есть, если первый операнд (words[0]) является истиной, он возвращает первый операнд. Если это falsy, возвращается второе...

Harsh Mishra
9 августа 2021 в 14:06
0

Ой. Понятно. Большое вам спасибо за вашу помощь.

avatar
Miguel Mont
29 апреля 2022 в 05:32
0

Это так же просто, как один цикл и сравнение каждого элемента строк

const longestPrefix = (strs) => {
[word1, word2, word3] = strs;
let prefix = [];
if(strs === null || strs.length <= 2 || strs.length > 3) return 'please 
insert 3 elements'

for (let i=0; i < word1.length; i++){ 
        if(word1[i] ===  word2[i] && word1[i] === word3[i]){
            prefix.push(word1[i])
        }
}
return prefix.join('')
}
avatar
Aman Pal
23 апреля 2022 в 06:04
0
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int main()
{
    char chr[50];
    printf("Enter string to get common letters :");
    gets(chr);
    char *token = strtok(chr, " ");
    char *arr[10];
    int i=0;
    while (token != NULL)
    {
        arr[i]=token;
        i++;
        token = strtok(NULL, " ");
    }
    char *var;
    int k=0,l=0;
    char temp, temp2;
    for(int j=0;j<=i;j++){
        var = arr[j];
        temp=var[k];
        var = arr[j+1];
        temp2=var[k];
        if(temp == temp2){
             if(i==j+2){
                j=-1;
                k++;
                printf("%c", temp);
                continue;
             }
             continue;
        }
    }
    return 0;
}
avatar
Nikita Patil
4 декабря 2021 в 06:50
0
var longestCommonPrefix = function(strs) {
    let prefix = "";
    for(let i = 0; i < strs[0].length; i++) {
        for(let j = 1; j < strs.length; j++) {
            if(strs[j][i] !== strs[0][i]) return prefix;
        }
        prefix = prefix + strs[0][i];
    }
    return prefix;
};
console.log(longestCommonPrefix);
Elikill58
4 декабря 2021 в 10:27
1

Можете ли вы просто объяснить, что вы изменили и почему ваш ответ решит проблему?

avatar
Tyler
25 сентября 2021 в 02:22
0

function prefixLen(s1, s2) {
    let i = 0;
    while (i <= s1.length && s1[i] === s2[i]) i++;
    return i;
}

function commonPrefix(arr) {
    let k = prefixLen(arr[0], arr[1]);
    for (let i = 2; i < arr.length; i++) {
        k = Math.min(k, prefixLen(arr[0], arr[i]));
    }
    return arr[0].slice(0, k);
}

console.log(commonPrefix(['pirate', 'pizza', 'pilates']))  // -> "pi"
avatar
Tal
10 сентября 2021 в 12:11
0

Я предполагаю, что вы здесь для решения проблемы Leetcode.

var longestCommonPrefix = function(strs) {
let arr = strs.concat().sort();
const a1 = arr[0];
const a2 = arr[arr.length -1];
const length = a1.length;
let i=0;

while(i<length && a1.charAt(i) == a2.charAt(i)) i++;
return a1.substring(0,i);

};
avatar
twf
4 сентября 2021 в 08:39
0

Увеличивать индекс, пока буква одинакова в этом индексе для всех слов в списке. Затем нарежьте его.

function prefix(words) {
  if (words.length === 0) { return '' }
  let index = 0;
  while (allSameAtIndex(words, index)) {
    index++;
  }
  return words[0].slice(0, index);
}

function allSameAtIndex(words, index) {
  let last;
  for (const word of words) {
    if (last !== undefined && word[index] !== last[index]) {
      return false;
    }
    last = word;
  }
  return true;
}
avatar
Peter Seliger
9 августа 2021 в 00:00
1

Подход, основанный на сортировке по длине слова, а для самого короткого слова, для раннего выхода, полностью Array.everyпрефикс-валидация и -агрегация ...

function longestCommonPrefix(arr) {
  const charList = [];

  const [shortestWord, ...wordList] =
    // sort shallow copy by item `length` first.
    [...arr].sort((a, b) => a.length - b.length);

  shortestWord
    .split('')
    .every((char, idx) => {
      const isValidChar = wordList.every(word =>
        word.charAt(idx) === char
      );
      if (isValidChar) {
        charList.push(char);
      }
      return isValidChar;
    });

  return charList.join('');
}

console.log(
  longestCommonPrefix(["flower","flow","flight"])
);
.as-console-wrapper { min-height: 100%!important; top: 0; }
avatar
hanshenrik
8 августа 2021 в 20:03
1

не лучшее решение, но должно сработать

function longestPrefix(strs){
    if(strs.length <1){
        return "";
    }
    const sharedPrefix=function(str1,str2){
        let i=0;
        for(;i<Math.min(str1.length,str2.length) /*todo optimize*/;++i){
            if(str1[i] !== str2[i]){
                break;
            }
        }
        return str1.substr(0,i);
    };
    let curr = strs[0];
    for(let i=1;i<strs.length;++i){
        curr=sharedPrefix(curr,strs[i]);
        if(curr.length < 1){
            // no shared prefix
            return "";
        }
    }
    return curr;
}
avatar
trincot
8 августа 2021 в 17:04
3

Некоторые проблемы:

  • Ваш внутренний цикл встретит return на своей первой итерации. Это означает, что ваши циклы никогда не будут повторяться, а возвращаемое значение всегда будет одним символом.

  • Неправильно адресовать strs[i+1] и strs[i+2] в вашем цикле, так как эти индексы выйдут за пределы (>= strs.length)

Вместо посимвольного сравнения вы можете использовать сравнение подстроки (префикса) (в одной операции): это может показаться пустой тратой времени, но поскольку такое сравнение происходит "ниже" кода JavaScript, оно очень быстро (и как строка ограничение по размеру 200 символов, это нормально).

Алгоритм может начинаться с выбора существующей строки в качестве префикса, а затем сокращать ее каждый раз, когда во входных данных появляется строка, не имеющая префикса. В конце у вас останется общий префикс.

Хорошо начать с самой короткой строки в качестве начального префикса-кандидата, так как общий префикс, безусловно, не может быть длиннее этого.

var longestCommonPrefix = function(strs) {
    let prefix = strs.reduce((acc, str) => str.length < acc.length ? str : acc);
    
    for (let str of strs) {
        while (str.slice(0, prefix.length) != prefix) {
            prefix = prefix.slice(0, -1);
        }
    }
    return prefix;
};

let res = longestCommonPrefix(["flower","flow","flight"]);

console.log(res);
Harsh Mishra
8 августа 2021 в 18:01
0

Я думаю, вы берете первые две строки из массива. А что, если длина третьей строки меньше длины двух других? И, если можно, объясните, что означает эта строка for(let str of strs)?

trincot
8 августа 2021 в 18:05
0

Первая строка перебирает весь массив (используя reduce), чтобы найти самую короткую строку. См. for...of в документации mdn. Это просто цикл по всем значениям в массиве без необходимости поддерживать индексную переменную.

hanshenrik
8 августа 2021 в 20:13
0

лучшее решение, опубликованное до сих пор, хорошая работа! PS этот код дает сбой с пустым массивом, но правильное это поведение или нет, может быть предметом обсуждения;)

trincot
8 августа 2021 в 20:16
0

Это при условии, что массив будет иметь размер не менее 1, поэтому я не стал возиться с пустым массивом.

avatar
AlexUnited
8 августа 2021 в 16:55
0
let strs = ["flower", "flow", "flight"];

var longestCommonPrefix = function (strs) {
  for (let i = 0; i < strs.length; i++) {
    for (let j = 0; j < strs[i].length; j++) {
        console.log(strs[i+2][j]);
      if (strs[i][j] == strs[i + 1][j] && strs[i][j]  ==strs[i + 2][j]) {
        return (strs[i][j]);
        


      } else {
        return "0";
      }
    }
  }
};

console.log(longestCommonPrefix(strs));

Это **возврат ** f

avatar
Alberto Sinigaglia
8 августа 2021 в 16:40
1

это:

strs[i][j] == strs[i + 1][j] ==strs[i + 2][j]

не имеет смысла в JS... или, по крайней мере, не имеет смысла в том, что вы делаете... для этого вы должны использовать оператор &&, например:

strs[i][j] == strs[i + 1][j] && strs[i + 1][j] ==strs[i + 2][j]

В противном случае JS оценит первое условие, а затем оценит результат этой операции (либо true, либо false) с третьим значением

В дополнение к этому учтите, что вы зацикливаетесь с i по массиву, поэтому i также будет str.length - 1, но в условии, которое вы ссылаетесь на strs[i + 2][j], в этом случае будет strs[str.length + 1][j] что в вашем случае не имеет смысла.

О решении:
Вы должны учитывать, что префикс является общим для всех значений в массиве, поэтому вы можете принять во внимание одно значение и просто проверить, равны ли все остальные... наиболее очевидным является первое, и вы в конечном итоге примерно так:

let strs = ["flower", "flow", "flight", "dix"];

function longestCommonPrefix (strs) {
  // loop over the characters of the first element
  for (let j = 0; j < strs[0].length; j++) {
    // ignore the first elements since is obvious that is equal to itself
    for (let i = 1; i < strs.length; i++) {
       /* in case you have like 
        [
          'banana',
          'bana'
        ]
        the longest prefix is the second element
       */
       if(j >= strs[i].length){
         return strs[i]
       }
       // different i-th element
       if(strs[0][j] != strs[i][j]){
         return strs[0].substr(0, j)
       }
       
    }
  }
  // all good, then the first element is common to all the other elements
  return strs[0]
};

console.log(longestCommonPrefix(strs));
Mike 'Pomax' Kamermans
8 августа 2021 в 16:43
1

Объяснение почему не имеет смысла (поскольку первое == даст логическое значение, поэтому второе == всегда будет ложным) было бы хорошим редактированием.

Harsh Mishra
8 августа 2021 в 16:46
0

@Alberto Sinigaglia Большое спасибо за вашу помощь, и что я должен изменить в своем коде, чтобы я мог выполнить итерацию для следующей проверки символов? Пожалуйста, ознакомьтесь также с вопросом.

Harsh Mishra
8 августа 2021 в 16:47
0

@Mike'Pomax'Kamermans Большое спасибо за объяснение.

Alberto Sinigaglia
8 августа 2021 в 16:49
0

@Mike'Pomax'Kamermans В противном случае JS оценит первое условие, а затем оценит результат этой операции (истина или ложь) с третьим значением , недостаточно?

Alberto Sinigaglia
8 августа 2021 в 16:50
0

@HarshMishra Я опубликовал возможное решение

Harsh Mishra
8 августа 2021 в 17:00
0

@AlbertoSinigaglia Я проголосовал за ваш ответ. Таким образом, он делает его равным нулю. Не беспокойтесь, ваше решение - это то, что я искал. Спасибо за вашу помощь.

trincot
8 августа 2021 в 17:09
1

Это не правильное решение. Во-первых, он может вернуться до того, как просмотрит все строки... Например, ["ааа", "аааааа", "что"] должна привести к пустой строке, но этот код возвращает "аа".

hanshenrik
8 августа 2021 в 17:54
0

это решение не работает, ["flower", "flow", "flight", "dix"]; возвращает flo, хотя flower не имеет общего префикса с dix

Alberto Sinigaglia
9 августа 2021 в 00:43
0

@trincot да, вы правы, я опечатался i вместо j

Alberto Sinigaglia
9 августа 2021 в 00:43
0

@hanshenrik да, вы правы, я опечатался i вместо j

Alberto Sinigaglia
9 августа 2021 в 00:45
1

@HarshMishra имейте в виду, что была опечатка ... кстати, я бы посоветовал вам проверить ответ derpirscher, который довольно аккуратен