Байтовый вопрос для интервью, уберите его и спасибо~

внешний интерфейс алгоритм

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

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

Пример 1:

输入: ["flower","flow","flight"]
输出: "fl"

Пример 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

проиллюстрировать:

Все входные данные содержат только строчные буквыa-z.

Решение 1. Сравните по одному

Идеи решения проблемы:Сравните строки спереди назад, чтобы получить общий префикс

Рисунок для понимания:

Код:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    let prevs = strs[0]
    for(let i = 1; i < strs.length; i++) {
        let j = 0
        for(; j < prevs.length && j < strs[i].length; j++) {
            if(prevs.charAt(j) !== strs[i].charAt(j)) break
        }
        prevs = prevs.substring(0, j)
        if(prevs === "") return ""
    }
    return prevs
};

Временная сложность: O(s), s — сумма количества символов во всех строках.

Космическая сложность: O(1)

Решение 2. Требуется только самый длинный общий префикс самой большой и самой маленькой строки

Идеи решения проблемы:Получить максимальную и минимальную строки в массиве.Самый длинный общий префикс минимальной строки и максимальной строки также является общим префиксом других строк, то есть самым длинным общим префиксом массива строк

Примечание: Вот максимум и минимум (судя по ASCII-коду), к длине это не имеет никакого отношения,bбольше, чемa,acбольше, чемab,acбольше, чемabc, вы можете перейти в консоль браузера, чтобы увидеть

Напримерabc,abcd,ab,ac, наименьшийabс макс.acСамый длинный общий префикс также должен бытьabc,abcdобщий префикс

Рисунок для понимания:

Код:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    if(strs.length === 1) return strs[0]
    let min = 0, max = 0
    for(let i = 1; i < strs.length; i++) {
        if(strs[min] > strs[i]) min = i
        if(strs[max] < strs[i]) max = i
    }
    for(let j = 0; j < strs[min].length; j++) {
        if(strs[min].charAt(j) !== strs[max].charAt(j)) {
            return strs[min].substring(0, j)
        }
    }
    return strs[min]
};

Временная сложность: O(n+m), n — длина массива, m — длина самого короткого символа в массиве строк.

Космическая сложность: O(1)

Решение 3. Стратегия «разделяй и властвуй» Объединение идей

Разделяй и властвуй, как следует из названия, означает «разделяй и властвуй», разделяй сложную проблему на две или более похожие подзадачи и разделяй подзадачи на меньшие подзадачи до тех пор, пока меньшие подзадачи не смогут быть просто решены. Решите подзадачи. Тогда решение исходной задачи представляет собой комбинацию решений подзадач.

Эта проблема является типичной задачей стратегии «разделяй и властвуй»:

  • Вопрос: Найдите самый длинный общий префикс нескольких строк
  • Разложить на несколько похожих подзадач: найти самый длинный общий префикс двух строк.
  • Подзадачи решаются просто: самый длинный общий префикс двух строк решается легко
  • Решение исходной проблемы представляет собой комбинацию решений подзадачи: самый длинный общий префикс нескольких строк является самым длинным общим префиксом самого длинного общего префикса двух строк Мы можем объединить и сравнить самый длинный общий префикс двух строк. самые длинные строки общего префикса. Общий префикс, пока он не будет окончательно объединен и сравнен в один, является самым длинным общим префиксом массива строк:LCP(S1, S2, ..., Sn) = LCP(LCP(S1, Sk), LCP(Sk+1, Sn))

Рисунок для понимания:

кabc,abcd,ab,acНапример:

Код:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    return lCPrefixRec(strs)
};

// 若分裂后的两个数组长度不为 1，则继续分裂
// 直到分裂后的数组长度都为 1，
// 然后比较获取最长公共前缀
function lCPrefixRec(arr) {
  let length = arr.length
  if(length === 1) {
    return arr[0]
  }
  let mid = Math.floor(length / 2),
      left = arr.slice(0, mid),
      right = arr.slice(mid, length)
  return lCPrefixTwo(lCPrefixRec(left), lCPrefixRec(right))
}

// 求 str1 与 str2 的最长公共前缀
function lCPrefixTwo(str1, str2) {
    let j = 0
    for(; j < str1.length && j < str2.length; j++) {
        if(str1.charAt(j) !== str2.charAt(j)) {
            break
        }
    }
    return str1.substring(0, j)
}

Временная сложность: O(s), s — сумма количества символов во всех строках.

Пространственная сложность: O(m*logn), n — длина массива, m — длина самого длинного символа в массиве строк.

Решение 4. Дерево Trie (дерево словарей)

Дерево Trie, также известное как дерево словарей или дерево префиксов, как следует из названия, представляет собой структуру данных, используемую для решения проблем сопоставления строк, и структуру данных, используемую для решения проблемы поиска строк с фиксированным префиксом в наборах.

Идеи решения проблемы:Чтобы построить дерево Trie, самая длинная общая последовательность строковых массивов состоит в обходе дерева от корневого узла до:

  • Обход узла, который имеет более одного дочернего узла

  • или пройти узел как конечный символ строки

Пока переданные символы являются самым длинным общим префиксом массива строк.

Рисунок для понимания:

Постройте дерево Trie дляabc,abcd,ab,acНапример:

Код:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    // 初始化 Trie 树
    let trie = new Trie()
    // 构建 Trie 树
    for(let i = 0; i < strs.length; i++) {
        if(!trie.insert(strs[i])) return ""
    }
    // 返回最长公共前缀
    return trie.searchLongestPrefix()
};
// Trie 树
var Trie = function() {
    this.root = new TrieNode()
};
var TrieNode = function() {
    // next 放入当前节点的子节点
    this.next = {};
    // 当前是否是结束节点
    this.isEnd = false;
};
Trie.prototype.insert = function(word) {
    if (!word) return false
    let node = this.root
    for (let i = 0; i < word.length; i++) {
        if (!node.next[word[i]]) {
            node.next[word[i]] = new TrieNode()
        }
        node = node.next[word[i]]
    }
    node.isEnd = true
    return true
};
Trie.prototype.searchLongestPrefix = function() {
    let node = this.root
    let prevs = ''
    while(node.next) {
        let keys = Object.keys(node.next)
        if(keys.length !== 1) break
        if(node.next[keys[0]].isEnd) {
            prevs += keys[0]
            break
        }
        prevs += keys[0]
        node = node.next[keys[0]]
    }
    return prevs
}

Временная сложность: O(s+m), s — сумма количества символов во всех строках, m — длина самого длинного символа в массиве строк, O(s) требуется для построения дерева Trie, а самая длинная операция запроса с общим префиксом Сложность O(m)

Пространственная сложность: O(s) для построения дерева Trie

наконец

Добро пожаловать, чтобы обратить внимание на «Front-end Bottle Master», ответьте на «Exchange», чтобы присоединиться к группе внешнего обмена!

Добро пожаловать, чтобы обратить внимание на «Front-end Bottle Master», ответьте «Алгоритм», чтобы автоматически присоединиться и построить полную структуру данных и систему алгоритмов от 0 до 1!

Здесь мистер Боттл не только представляет алгоритм, но и объединяет алгоритм с различными полями интерфейса, включая браузеры, HTTP, V8, React, исходный код Vue и т. д.

Здесь (группа алгоритмов) вы можете изучать большой вопрос по программированию заводского алгоритма (Ali, Tencent, Baidu, Byte и т. д.) или литкод каждый день, а мистер Бутылка ответит на него на следующий день!

Кроме того, каждую неделю есть рукописные вопросы по исходному коду, и мистер Боттл тоже на них ответит!

Категории