Home > Reflections | ⏮️ ⏭️

2024-04-28

🏋🏻 Practice

A few solutions to a simple programming problem: Longest Common Prefix.

/*  
Longest common prefix  
Seems easy  
1. Initialize to the empty string  
2. Check the first character of each string  
3. If they're all the same, add it to the result  
4. Repeat this until we don't get a match or we run out of string  
5. Return the result  
*/  
function longestCommonPrefix1(strs: string[]): string {  
  let result = ""  
  let i = 0  
  let ranOutOfString = false  
  let uncommonPrefix = false  
  while (true) {  
    for (let s = 0; s < strs.length; s++) {  
      const string = strs[s]  
      if (string.length < (i + 1)) {  
        ranOutOfString = true  
        break  
      }  
      if (string[i] !== strs[0][i]) {  
        uncommonPrefix = true  
        break  
      }  
    }  
    if (ranOutOfString || uncommonPrefix) {  
      break  
    }  
    result = result + strs[0][i]  
    i++  
  }  
  return result  
}  
  
// We don't need an unbounded while-loop if we iterate over the indices of the shortest string  
function longestCommonPrefix2(strings: string[]): string {  
  const shortest = strings.reduce((a, b) => a.length < b.length ? a : b)  
  let result = ""  
  for (let i = 0; i < shortest.length; i++) {  
    if (strings.every(s => s[i] === shortest[i])) {  
      result += shortest[i]  
    } else {  
      break  
    }  
  }  
  return result  
}  
  
// We don't need to repeatedly modify a string if we just find the first unshared index  
function longestCommonPrefix3(strings: string[]): string {  
  const shortest = strings.reduce((a, b) => a.length < b.length ? a : b)  
  const firstUnsharedIndex = shortest.split('').map((x, i) => i)  
    .find(i => strings.some(s => s[i] !== shortest[i]))  
  return shortest.slice(0, firstUnsharedIndex)  
}  
  
// We don't need to explicitly find the shortest string first if we check length as we go  
function longestCommonPrefix4(strings: string[]): string {  
  const firstUnsharedIndex = strings[0].split('').map((x, i) => i)  
    .find(i => strings.some(s => s.length <= i || s[i] !== strings[0][i]))  
  return strings[0].slice(0, firstUnsharedIndex)  
}  
  
// With a simple for-loop, we can return as soon as we find the unshared index  
function longestCommonPrefix(strings: string[]): string {  
  for (let i = 0; i <= strings[0].length; i++) {  
    if (strings.some(s => s.length <= i || s[i] !== strings[0][i])) {  
      return strings[0].slice(0, i)  
    }  
  }  
}