Problem description:

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:

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

Example 2:

1
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.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
#         str=["flower","flow","flight"]

#         after zip(*strs)
#         [('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]

#         taken first set
#         len(set( "f","f","f"))=1

#         and taken 3
#         len(set("o","o","i"))=2

        prefix = []
        num = len(strs)
        for x in zip(*strs):
            if len(set(x)) == 1:
                prefix.append(x[0])
            else:
                break
        return "".join(prefix)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        //compare the firs two strings to find it's common, then use it to find others common
        if(strs.empty()) return "";
        string common= strs[0];
        for(int i= 1; i< strs.size(); i++){
            if(common == "") return common;
            int size= min(common.length(), strs[i].length());
            int c= 0;
            while( c< size){
                if(common[c] != strs[i][c])
                    break;
                c++;
            }
            common= common.substr(0, c);
        }
        return common;
        
    }
};

time complexity: $O()$
space complexity: $O()$
reference: