Home | Projects | Notes > Problem Solving > LC - E - 14. Longest Common Prefix

LC - E - 14. Longest Common Prefix

Solutions in C++

Solution 1

This solution takes the first string in the vector strs as a reference, and compares character by character throughout all the strings in strs.

Complexity Analysis:

• $T=O(mn)$$T = O(mn)$ where $m$$m$ is the shortest string, $n$$n$ is the number of strings in the given vector strs

• $S=O(1)$$S = O(1)$ as no additional memory is needed

Solution:

xxxxxxxxxx
18
1
class Solution {
2
public:
3
    string longestCommonPrefix(vector<string>& strs) {
4
        string ret;
5

6
        for (int j = 0; strs[0][j] != '\0'; j++) 
7
        {
8
            for (int i = 0; i < strs.size(); i++)
9
            {
10
                if (strs[i][j] != strs[0][j])
11
                    return ret;
12
            }
13
            ret += strs[0][j];
14
        }
15

16
        return ret;
17
    }
18
};

line 6: Termination condition can also be written as strs[0].length().

• For the operator [], the position after the last character is valid index. It will return the value that is generated by the default constructor of the character type which is ‘\0’.

  However, for at(), the position after the last character is NOT valid. It will throw an out_of_range exception when it reaches that position.

  xxxxxxxxxx
  5
  1
  strs[0].at(i);    // throws an exception when i hits the position after the last 
  2
                    // character
  3
  
  4
  strs[0][i];       // returns '\0' when i reaches the position after the last
  5
                    // character