Skip to content

Latest commit

 

History

History
42 lines (35 loc) · 1.06 KB

14.最长公共前缀.md

File metadata and controls

42 lines (35 loc) · 1.06 KB

14.最长公共前缀

/*
 * @lc app=leetcode.cn id=14 lang=typescript
 *
 * [14] 最长公共前缀
 */

// @lc code=start
function longestCommonPrefix(strs: string[]): string {}
// @lc code=end

解法 1: 广度优先搜索

  • 时间复杂度: O(m*n)
  • 空间复杂度: O(1)
function longestCommonPrefix(strs: string[]): string {
  let [res, i, tmp] = ['', 0, '']
  while (true) {
    for (const s of strs) {
      if (tmp === '') tmp = s[i]
      if (s[i] === undefined || s[i] !== tmp) return res
    }
    ;[res, i, tmp] = [res + tmp, i + 1, '']
  }
}

Case

test.each([
  { input: { strs: ['flower', 'flow', 'flight'] }, output: 'fl' },
  { input: { strs: ['dog', 'racecar', 'car'] }, output: '' },
])('input: strs = $input.strs', ({ input: { strs }, output }) => {
  expect(longestCommonPrefix(strs)).toBe(output)
})