Code and approach to so solve Longest common prefix

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        Longest_sum = ""

        for i in range(len(strs[0])):
            for j in strs:
                if i >= len(j) or j[i] != strs[0][i]:
                    return Longest_sum

            Longest_sum += strs[0][i]

        return Longest_sum

Enter fullscreen mode Exit fullscreen mode

PROBLEM

so in the ques we have given an array of strings strs and we have to find the longest common prefix among all the strings.

prefix means the characters that come at the starting of the string.

like here strs = [“flower”,”flow”,”flight”].

the common starting characters are f, l, so the longest common prefix is “fl”.

therefore the answer will be “fl”.

APPROACH

so here we create an empty string Longest_sum where we will store the common prefix.

then we loop through the characters of the first string because we can use the first string as a reference and compare its characters with all the other strings.

then inside that loop, we loop through every string in strs.

for every string we check two conditions:

i >= len(j)

this checks if the current index i is outside the length of the current string. If it is, then there cannot be any common prefix at this position.

and:

j[i] != strs[0][i]

this checks if the current character of the string is different from the character at the same position in the first string.

if either condition is true, it means the common prefix has ended, so we return Longest_sum.

if the character is the same in every string, we add that character to Longest_sum and continue checking the next character.

for example:

strs = [“flower”,”flow”,”flight”]

first character:

f == f == f -> add f

second character:

l == l == l -> add l

third character:

o == o but o != i -> stop

so Longest_sum = “fl” and we return “fl”.

CODE EXPLAINATION

strs = ["flower","flow","flight"]

Longest_sum = ""  -> creating an empty string Longest_sum where we will store the common prefix.

for i in range(len(strs[0])): -> looping through the indices of the first string.

we use the first string as a reference and check its characters against all the other strings.
for strs = ["flower","flow","flight"], the loop checks index 0, 1, 2, and so on.

for j in strs:  -> looping through every string in strs so we can compare the character at index i with the character from the first string.

if i >= len(j) or j[i] != strs[0][i]:
    return Longest_sum  -> checking if the current index is outside the length of the current string or if the characters are different.

i >= len(j) means the current string is shorter and does not have a character at index i.

j[i] != strs[0][i] means the current character is different from the character at the same position in the first string.

if either condition is true, the common prefix ends here, so we return Longest_sum.

Longest_sum += strs[0][i]  -> if the current character is the same in every string, we add that character to Longest_sum.

for example:

Longest_sum = ""

then f -> "f"

then l -> "fl"

then when the characters don't match, we return "fl".

return Longest_sum  -> if we finish checking the first string without finding a mismatch, we return the complete Longest_sum as the longest common prefix.

Enter fullscreen mode Exit fullscreen mode