Welcome back! This lesson will shift our focus to advanced string manipulation. String manipulation is one of the most fundamental skill sets necessary for tackling real-world programming problems. Understanding these principles is essential as they help break down complex problems into simpler ones. It also improves one's adaptability in situations where the specific language syntax might not be readily available.

Let's jump right into a common coding interview challenge. This challenge requires creating a function longestCommonPrefix, that finds the longest common starting sequence of characters (prefix) shared among all strings in a given vector of strings. For instance, the longest common prefix of {"flower", "flow", "flight"} is fl.

Our approach to this challenge is:

1. Check for Empty Input: If the input vector of strings is empty, the function returns an empty string, as there are no strings to compare.
2. Identify the Shortest String: Finding the shortest string optimizes our function by limiting the number of comparisons in the next step.
3. Character by Character Comparison: Compare characters of the shortest string with the corresponding characters in all other strings.
   • For each character index i of the shortest string, store the character in charToCheck.
   • Iterates over all strings in the vector to check if the character at index i matches charToCheck. If a mismatch is found, return the substring of shortest from the start up to (but excluding) index i.
4. Return the Shortest String: If no mismatch is found after checking all characters of the shortest string, the function returns the shortest string itself as the longest common prefix.

Let's use this algorithm for the input {"flower", "flow", "flight"}.

1. The vector is not empty
2. The function identifies "flow" as the shortest string among the input strings.
3. Start comparing each character of "flow" with the corresponding characters in the other strings:
   • At index 0, all strings have 'f'.
   • At index 1, all strings have 'l'.
   • At index 2, "flower" and "flow" have 'o' but "flight" has 'i', resulting in a mismatch.
4. Since a mismatch is found at index 2, the function returns the substring of "flow" from the start up to index 2, which is "fl".

The translation of this algorithm to C++ is:

C++
Copy to clipboard
1#include <iostream>
2#include <vector>
3#include <string>
4
5std::string longestCommonPrefix(const std::vector<std::string>& strs) {
6    if (strs.empty()) return "";
7    
8    std::string shortest = strs[0];
9    for (const std::string& str : strs) {
10        if (str.size() < shortest.size()) {
11            shortest = str;
12        }
13    }
14
15    for (size_t i = 0; i < shortest.size(); i++) {
16        char charToCheck = shortest[i];
17        for (const std::string& str : strs) {
18            if (str[i] != charToCheck) {
19                return shortest.substr(0, i);
20            }
21        }
22    }
23    return shortest;
24}
25
26int main() {
27    std::vector<std::string> strs = {"flower", "flow", "flight"};
28    std::cout << longestCommonPrefix(strs) << std::endl;  // Outputs: "fl"
29    return 0;
30}

Let's break down the longestCommonPrefix function step by step:

Function Definition

This line defines the function longestCommonPrefix that returns a std::string. The parameter is a constant reference to an std::vector containing std::string.

C++
Copy to clipboard
1std::string longestCommonPrefix(const std::vector<std::string>& strs)

Check for Empty Input

This check ensures that if the input vector of strings is empty, the function immediately returns an empty string, as there is no common prefix to find.

C++
Copy to clipboard
1if (strs.empty()) return "";

Identify the Shortest String

This step initializes the shortest string to the first string in the input vector. It then iterates through the vector to find the string with the smallest length. This helps limit the number of character comparisons needed in the next step.

C++
Copy to clipboard
1std::string shortest = strs[0];
2for (const std::string& str : strs) {
3    if (str.size() < shortest.size()) {
4        shortest = str;
5    }
6}

Character by Character Comparison

The first for loop iterates over each character index of the shortest string. For each character index i, it stores the character in charToCheck.

C++
Copy to clipboard
1for (size_t i = 0; i < shortest.size(); i++) {
2    char charToCheck = shortest[i];

Inner Loop for Comparison

The inner for loop iterates over all strings in the input vector to check if the character at index i in each string matches charToCheck. If a mismatch is found, the function returns the substring of shortest from the start up to (but excluding) index i.

C++
Copy to clipboard
1for (const std::string& str : strs) {
2    if (str[i] != charToCheck) {
3        return shortest.substr(0, i);
4    }
5}

Return the Shortest String

If no mismatch is found after checking all characters of the shortest string, the function returns the shortest string itself, as it is the longest common prefix.

C++
Copy to clipboard
1return shortest;

In our hands-on practice segment, we will delve deep into various string manipulation techniques. Don't worry if you feel overwhelmed; our goal here is step-by-step comprehension, not fast-paced learning. Our example problems delve into the intricacies of string manipulation, helping you to iteratively develop your own unique solving patterns and strategies. We aim to foster a deep understanding rather than rote memorization of algorithms. Let's dive in!