> For the complete documentation index, see [llms.txt](https://kseb0.gitbook.io/whiteboard/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kseb0.gitbook.io/whiteboard/arrays-and-strings/longest-common-prefix.md).

# Longest Common Prefix

### Approach1: Vertical Scanning

This approach consists of iterating  over the characters of an arbitrarily chosen String from the array  (in this example, we use the string at `index 0`) and verify by looping on each of the Strings of the array if they contain that same character at the position specified by the initially chosen String (*Outer Loop*).

* Iterate over first String of given array (*in lieu of a traditionnal loop or a for-each loop, we use enumerate to simultaneously get the position of the pointer as well as the character it is pointing to.*)
* We loop over the Strings of the array and check whether they have the same character at position `i` then `strs[0]`. 
* We stop the loop for the below conditions:
  *  If `i` equals or surpasses the length of a given word meaning that there cannot be a longer common prefix, we then return the substring.
  * If the chracters are different at position `i` , we return the `substring[0:i]` indicating that it is the longest prefix shared by all the strings constituting the array.<br>

```python
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        for i, ch in enumerate(strs[0]):
            for word in strs:
                if i >= len(word) or word[i] != ch:
                    return word[:i]
        return strs[0]
```

**`Time: O(mn)       m = Length of longest String   n = length of array strs.    Space: O(1)`**

### Java Version of Vertical Scanning

```java
class Solution {
    //Vertical Scanning
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0) return "";
        StringBuilder sb = new StringBuilder();
        
        for(int i = 0; i < strs[0].length(); i++){
            char c = strs[0].charAt(i);
            for(int j = 1; j < strs.length; j++){
                if(i >= strs[j].length() || strs[j].charAt(i) != c){
                    return sb.toString();
                }
            }
            sb.append(c);
        }
        return sb.toString();
    }
}
```

### Approach2: Horizontal Scanning&#x20;

The code for this approach as well as it's underlying concept is relatively easier to grasp than the above.&#x20;

* We again select the first String (strs\[0]) and reference it to a string holder called `pre.`&#x20;
* We then loop over each subsequent Strings in the array and check whether or not they start with `pre.`
* If the String does not start with `pre,` we subseqently reduce it by one index from the right by getting it's substring. We use the while loop as we want to ensure that for each iteration, `pre` is being reduced until it is a prefix.

```java
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        pre = strs[0]
        
        for i in range(1, len(strs)):
            while not strs[i].startswith(pre):
                pre = pre[:-1]
        return pre
```

**`O(n`` `` `*****`m`*****` `` ``(m + m))`**, which is **`O(n`` `` `*****`m`*****` `` ``2m)`**, which is **`O(n * m^2)`** Because for **`n`** strings it does **`m`** times startswith (which is **`O(m))`** and m times substring (which is **`O(m)).`**

### Java Version of Vertical Scanning

```java
class Solution {
    //Horizontal Scanning
     if(strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for(int i = 0; i < strs.length; i++){
            while(strs[i].indexOf(prefix) != 0){
                prefix = prefix.substring(0, prefix.length() - 1);
                if(prefix.length() == 0) return "";
            }
        }
        return prefix;
    }
}
```

### &#x20;