14 Longest Common Prefix

title: Longest Common Prefix
tags:
- longest-common-prefix
- No.14
- simple
- loop-optimization
- string

Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

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

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Corner Cases

• ["a"]
• []

Solution

Naive

The worst case is that n strings are all the same with m length. Then the algorithm must check every char for all strings. So the running time is no less than O(mn), which indicates a
2-loop structure. Here two points about loop optimization.

1. Cache Friendly

Take advantage of the sequential storage in cache. Use

for (int i=0; i<10; i++) {
    for (int j=0; j<10; j++) {
        f(a[i][j]);
    }
}

instead of

for (int i=0; i<10; i++) {
    for (int j=0; j<10; j++) {
        f(a[j][i]);
    }
}

2. Branch Prediction

If there is only a binary assignment inside the loop like:

for (int i=0; i<10; i++) {
    if (a[i] > 0) {x += 5;}
    else          {       }
}

use boolean or other trick to avoid if-else staying in the loop, otherwise the computer archtecture would do branch prediction at a relative high cost:

for (int i=0; i<10; i++) {
    x += (a[i] > 0) * 5;
}

The running time is O(mn).

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {return "";}
        
        String a = strs[0];
        int    k = a.length();
        
        // O(mn)
        for (int i=1; i<strs.length; i++) {
            int l = (k < strs[i].length()) ? k : strs[i].length();            
            for (k=0; (k<l) && (strs[i].charAt(k) == a.charAt(k)); k++) {}
        }
                    
        return (k==0) ? "" : a.substring(0, k);
    }
}