Longest common prefix python

Задача “Longest Common Prefix” с LeetCode, решение на Python

Напишите функцию для поиска самой длинной строки общего префикса среди массива строк.

Если общего префикса нет, верните пустую строку «» .

© LeetCode Problems

Пример входных и выходных данных программы от LeetCode:

Ввод: strs = ["цветок", "поток", "полет"] Вывод: "fl"

Ограничения, которые предоставляет LeetCode:

Решение Longest Common Prefix, полный код:

class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" for i in range(len(strs[0])): for j in range(1, len(strs)): if i >= len(strs[j]) or strs[j][i] != strs[0][i]: return strs[0][:i] return strs[0]

Разбор решения Longest Common Prefix с LeetCode

Функция longestCommonPrefix находит наибольший общий префикс в списке строк strs и возвращает его в виде строки. Если список strs пуст, то функция возвращает пустую строку.

Алгоритм решения этой задачи работает следующим образом:

1. Если входной список strs пуст, то вернуть пустую строку.
2. Произвести итерацию по символам в первой строке списка strs[0] с помощью цикла for i in range(len(strs[0])) .
3. Вложенным циклом for j in range(1, len(strs)) произвести итерацию по остальным строкам списка strs начиная со второй.
4. В каждой итерации проверить, если индекс i больше или равен длине строки strs[j] , то вернуть префикс первой строки strs[0] с длиной i .
5. Если символ строки strs[j] с индексом i не равен символу строки strs[0] с индексом i , то вернуть префикс первой строки strs[0] с длиной i .
6. Если обе проверки в пунктах 4 и 5 не выполняются, то продолжить выполнение внутреннего цикла for j in range(1, len(strs)) .
7. Если выполнение внутреннего цикла for j in range(1, len(strs)) завершилось успешно без прерывания на шагах 4 или 5, то вернуть первую строку strs[0] в качестве общего префикса.

Источник

LeetCode #14 — Longest Common Prefix

Hello fellow devs 👋! Today we will discuss another LeetCode problem.

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 «».

• 0 ≤ strs.length ≤ 200
• 0 ≤ strs[i].length ≤ 200
• strs[i] consists of only lower-case English letters.

Input: strs = ["flower","flow","flight"] Output: "fl"

Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

As per the question, we will be given an array of some strings which can be of varying lengths. We only have to find first n characters which appear in each string between the indices 0 and n — 1 .

It is clear that the common characters cannot be more than the length of the shortest string of all the given strings. Therefore, we will first find the shortest string amongst all strings and check maximum characters of it are present in all the other strings.

If not a single character is present in all the other string, we will return an empty string.

The approach is pretty simple —

1. First we will find the shortest string and its length.
2. Secondly, we will take the first string and match its each character one by one with all the other strings.
3. As soon as we encounter a character which does not match, we will break out of loop.

If n is the length of the array and m is the length of the shortest string, the worst case time complexity will be O(m × n).

Since we are not using any internal data structure for intermediate computations, the space complexity will be O(1).

public class LongestCommonPrefix  public String longestCommonPrefix(String[] strs)  // Longest common prefix string StringBuilder longestCommonPrefix = new StringBuilder(); // Base condition if (strs == null || strs.length == 0)  return longestCommonPrefix.toString(); > // Find the minimum length string from the array int minimumLength = strs[0].length(); for (int i = 1; i  strs.length; i++)  minimumLength = Math.min(minimumLength, strs[i].length()); > // Loop for the minimum length for (int i = 0; i  minimumLength; i++)  // Get the current character from first string char current = strs[0].charAt(i); // Check if this character is found in all other strings or not for (String str : strs)  if (str.charAt(i) != current)  return longestCommonPrefix.toString(); > > longestCommonPrefix.append(current); > return longestCommonPrefix.toString(); > >

def longestCommonPrefix(strs: List[str]) -> str: # Longest common prefix string lcp = "" # Base condition if strs is None or len(strs) == 0: return lcp # Find the minimum length string from the array minimumLength = len(strs[0]) for i in range(1, len(strs)): minimumLength = min(minimumLength, len(strs[i])) # Loop until the minimum length for i in range(0, minimumLength): # Get the current character from the first string current = strs[0][i] # Check if this character is found in all other strings or not for j in range(0, len(strs)): if strs[j][i] != current: return lcp lcp += current return lcp

var longestCommonPrefix = function (strs)  // Longest common prefix string let longestCommonPrefix = ""; // Base condition if (strs == null || strs.length == 0)  return longestCommonPrefix; > // Find the minimum length string from the array let minimumLength = strs[0].length; for (let i = 1; i  strs.length; i++)  minimumLength = Math.min(minimumLength, strs[i].length); > // Loop for the minimum length for (let i = 0; i  minimumLength; i++)  // Get the current character from first string let current = strs[0][i]; // Check if this character is found in all other strings or not for (let j = 0; j  strs.length; j++)  if (strs[j][i] != current)  return longestCommonPrefix; > > longestCommonPrefix += current; > return longestCommonPrefix; >;

fun longestCommonPrefix(strs: ArrayString>): String  // Longest common prefix string val longestCommonPrefix = StringBuilder() // Base condition if (strs.isEmpty())  return longestCommonPrefix.toString() > // Find the minimum length string from the array var minimumLength = strs[0].length for (i in 1 until strs.size)  minimumLength = minimumLength.coerceAtMost(strs[i].length) > // Loop for the minimum length for (i in 0 until minimumLength)  // Get the current character from first string val current = strs[0][i] // Check if this character is found in all other strings or not for (str in strs)  if (str[i] != current)  return longestCommonPrefix.toString() > > longestCommonPrefix.append(current) > return longestCommonPrefix.toString() >

Congratulations 👏! We have solved another problem from LeetCode.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.

Till next time… Happy coding 😄 and Namaste 🙏!

Источник

Longest Common Prefix using Python

Longest Common Prefix is one of the popular problems in Leetcode. It is asked in coding interviews by companies like FAANG many times. Here you need to return the longest common prefix among all the strings in an array of strings. So, if you want to learn how to solve the Longest Common Prefix problem, this article is for you. In this article, I will take you through how to solve the Longest Common Prefix problem using Python.

Longest Common Prefix using Python

To solve the Longest Common Prefix problem, you need to find the most common prefix in all the strings of an array. For example, you are given an array of strings [“flower”, “flow”, “flight”], in this array, the most common prefix among the first two items is “flo”, so, if the third element would have been “flowing”, then the longest common prefix would have been “flo”. But as the common prefix among all the strings of the array is “fl”, the output should return “fl”.

I hope you now have understood what the longest common prefix means. Now here’s how to solve this problem using the Python programming language:

strs = ["flower", "flow", "flight"] def longestCommonPrefix(strs): l = len(strs[0]) for i in range(1, len(strs)): length = min(l, len(strs[i])) while length > 0 and strs[0][0:length] != strs[i][0:length]: length = length - 1 if length == 0: return 0 return strs[0][0:length] print(longestCommonPrefix(strs))

So this is how you can solve this problem using Python. You can find many more practice questions to improve your problem-solving skills using Python here.

Summary

To solve the Longest Common Prefix problem, you need to find the most common prefix in all the strings of an array. For example, in an array of strings [“flower”, “flow”, “flight”], the most common prefix is “fl”. I hope you liked this article on finding the longest common prefix using Python. Feel free to ask valuable questions in the comments section below.

Источник