Technology Sharing

Algorithm: String Correlation

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Table of contents

Question 1: Longest common prefix

Question 2: The longest palindrome substring

Problem 3: Binary sum

Problem 4: String multiplication

Question 1:Longest common prefix

Write a function to find the longest common prefix in an array of strings

If there is no common prefix, returns an empty string""

Example 1:

输入：strs = ["flower","flow","flight"]
输出："fl"

Example 2:

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

hint:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i]Only lowercase English letters

Solution 1: Pairwise comparison

Solution 1 is a two-by-two comparison strategy. First, compare the first two strings. After the comparison, compare the common prefix of the first two strings with the third string to get the common prefix of the first three strings, and so on.

code show as below:

  1. class Solution 
  2. {
  3. public:
  4.     string findCommon(string& s1, string& s2)
  5.     {
  6.         int i = 0;
  7.         //i有可能会出现越界的情况，所以i小于s1s2长度时再循环判断
  8.         while(i < min(s1.size(), s2.size()) && s1[i] == s2[i])
  9.             i++;
  10.         return s1.substr(0, i);
  11.     }
  12.  
  13.     string longestCommonPrefix(vector<string>& strs) 
  14.     {
  15.         int n = strs.size();
  16.         //same字符串就是存储最长公共前缀的字符串
  17.         string same = strs[0];
  18.         for(int i = 1; i < n; i++)
  19.             same = findCommon(same, strs[i]);
  20.         return same;
  21.     }
  22. };

Solution 2: Unified comparison

Unified comparison means comparing the same position of all strings at once to determine whether the position is the same until different characters appear.

There will be an out-of-bounds situation here, which means that a certain string has ended, so the comparison can be terminated.

code show as below:

  1. class Solution 
  2. {
  3. public:
  4.     string longestCommonPrefix(vector<string>& strs) 
  5.     {
  6.         int i = 0;
  7.         //以第一个字符串为基准，与其他所有字符串做比较
  8.         for(i = 0; i < strs[0].size(); i++)
  9.         {
  10.             //ch表示第一个字符串当前循环到的字符
  11.             char ch = strs[0][i];
  12.             //循环strs中其余的字符串，其余字符串的i位置字符与ch做比较
  13.             for(int j = 1; j < strs.size(); j++)
  14.             {  
  15.                 //如果i大于当前字符串的长度，说明当前字符串已经没有元素了
  16.                 if(i > strs[j].size() || strs[j][i] != ch)
  17.                     return strs[0].substr(0, i);
  18.             }
  19.         }
  20.         return strs[0];
  21.     }
  22. };

Question 2:Longest palindrome substring

Give you a strings,turn upsThe longest palindrome in

Example 1:

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

Example 2:

输入：s = "cbbd"
输出："bb"

The ordinary brute force enumeration algorithm sets two pointers, one i and one j. Fix i and move j backward. Each time j is moved, it is necessary to determine whether the string between i and j is a palindrome substring. At this time, the time complexity of moving j and determining whether i and j are palindrome substrings is O(N^2). Because there is a layer of i nested outside to traverse the entire string, the time complexity of the entire brute force enumeration is very high, reaching O(N^3). Let's look at the optimized center expansion algorithm:

Solution: Center-Extend Algorithm

The center-extend algorithm is:

①Fix a center point
② Start from the center point and expand to both sides (both odd and even lengths need to be considered)

That is, each time a central point i is fixed, each time it expands to the left and right of i, and determines whether it is a palindrome. The time complexity of this algorithm to traverse i is O(N), and the time complexity of nested expansion to the left and right of i is also O(N), so the final complexity is O(N^2), which is much more optimized than the brute force solution mentioned above.

What needs to be noted is the second point of the center expansion algorithm. We need to consider odd and even numbers, because odd numbers move the left and right pointers from position i to the left and right, while even numbers require left to be at position i and right to be at position i + 1, and then move left and right again.

It should be noted that the length in the code is right - left - 1, because if the elements currently pointed to by left and right are the same, left-- and right++ need to be changed. If they are not the same, the loop will be exited. Therefore, both left and right are moved one more position than the palindrome, so the length is calculated as right - left - 1. See the figure below for details:

As shown in the figure above, the loop exits when left and right point to the current position, so the length of the palindrome substring aa is:
right - left - 1 = 3 - 0 - 1 = 2

code show as below:

  1. class Solution 
  2. {
  3. public:
  4.     string longestPalindrome(string s) 
  5.     {
  6.         if(s.size() == 1) return s;
  7.         int n = s.size(), begin = 0, size = 0;
  8.         for(int i = 0; i < n; i++)
  9.         {
  10.             //先做奇数长度的扩展
  11.             int left = i, right = i;
  12.             //left和right符合条件，且指向元素相等再进入循环
  13.             while(left >= 0 && right < n && s[left] == s[right])
  14.             {
  15.                 --left;
  16.                 ++right;
  17.             }
  18.             //如果长度更大，更新begin与size
  19.             if((right - left - 1) > size)
  20.             {
  21.                 size = right - left - 1;
  22.                 begin = left + 1;
  23.             }
  24.             //再做偶数长度的扩展
  25.             left = i, right = i + 1;
  26.             //left和right符合条件，且指向元素相等再进入循环
  27.             while(left >= 0 && right < n && s[left] == s[right])
  28.             {
  29.                 --left;
  30.                 ++right;
  31.             }
  32.             //如果长度更大，更新begin与size
  33.             if((right - left - 1) > size)
  34.             {
  35.                 size = right - left - 1;
  36.                 begin = left + 1;
  37.             }            
  38.         }
  39.         return s.substr(begin, size);
  40.     }
  41. };

Question 3:Binary sum

Given two binary stringsaandb, returning their sum as a binary string.

Example 1:

输入:a = "11", b = "1"
输出："100"

Example 2:

输入：a = "1010", b = "1011"
输出："10101"

This question is to calculate high-precision addition, perform a simulation operation, and simulate the process of vertical calculation.

You need to set two pointers cur1 and cur2 to point to two strings respectively, and then set a variable t to represent the carry.

code show as below:

  1. class Solution 
  2. {
  3. public:
  4.     string addBinary(string a, string b) 
  5.     {
  6.         //t表示相加后的进位
  7.         int t = 0;
  8.         string ret;
  9.         int cur1 = a.size()-1, cur2 = b.size()-1;
  10.         //cur1或cur2 >= 0表示字符串没遍历完，t>0表示还剩一个进位
  11.         while(cur1 >= 0 || cur2 >= 0 || t)
  12.         {
  13.             if(cur1 >= 0) t += a[cur1--] - '0';  
  14.             if(cur2 >= 0) t += b[cur2--] - '0';
  15.             ret += to_string(t % 2);
  16.             t /= 2;
  17.         }
  18.         //从后向前加的，刚好反过来了，需要逆置
  19.         reverse(ret.begin(), ret.end());
  20.         return ret;
  21.     }
  22. };

Question 4:Multiplying Strings

Given two non-negative integers represented as stringsnum1andnum2,returnnum1andnum2The product of , their product is also expressed in string form.

Notice:You cannot use any built-in BigInteger library or directly convert the input to an integer.

Example 1:

输入: num1 = "2", num2 = "3"
输出: "6"

Example 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

Solution 1: Simulate vertical calculation

In mathematics, the vertical form of the multiplication column is the easiest method to think of.

As follows:

We can understand that each digit of the following 456 is multiplied by the above 123 and then added together. There are three details:

① High-order multiplication needs to be supplemented with 0, because one digit is wrong when adding 738 and 615, it can be understood as 738 + 6150
②Handle leading 0, there may be a situation where 123 × 0 occurs, in which case the answer is 000, which needs to be processed
③ Pay attention to the order of calculation results, because the calculation is done in reverse order, and multiplication starts from the last digit

But this method is not easy to write code, we need to use this method to optimize it

Solution 2: Optimize Solution 1

Multiply without carry and then add, and handle the carry in the last step:

That is, no matter how many numbers are multiplied, there is no carry, and the carry is done after the final addition.

Similarly, when starting the calculation, reverse the order first. Since the multiplication may be a two-digit number, it cannot be represented by a string. An array can be used to store it.

Since it is in reverse order, the subscripts corresponding to 123 are 2, 1, 0, and the subscripts corresponding to 456 are also 2, 1, 0

There is a very useful rule: multiply the numbers in the i and j subscripts, and the result is placed exactly at the i + j position in the array

①Define an array tmp with a length of m + n - 1 (m and n correspond to the length of the two multiplied numbers)
The subscripts of the two numbers being multiplied are i and j respectively, and the result of the calculation is placed at the i + j position of the array
②After the final addition, the carry needs to be processed
③Processing leading 0

code show as below:

  1. class Solution 
  2. {
  3. public:
  4.     string multiply(string num1, string num2) 
  5.     {
  6.         //先逆序两个字符串
  7.         reverse(num1.begin(), num1.end());
  8.         reverse(num2.begin(), num2.end());
  9.         //定义一个数组tmp
  10.         int m = num1.size(), n = num2.size();
  11.         vector<int> tmp(m + n - 1);
  12.         //无进位相乘然后相加
  13.         for(int i = 0; i < m; i++)
  14.             for(int j = 0; j < n; j++)
  15.                 tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
  16.         //处理进位
  17.         string ret;
  18.         int t = 0, cur = 0;
  19.         while(cur < m + n - 1 || t != 0)
  20.         {
  21.             if(cur < m + n - 1) t += tmp[cur++];
  22.             ret += to_string(t % 10);
  23.             t /= 10;
  24.         }
  25.         if(t) ret += to_string(t);
  26.         //处理前置0
  27.         while(ret.back() == '0' && ret.size() > 1) ret.pop_back();
  28.         reverse(ret.begin(), ret.end());
  29.  
  30.         return ret;
  31.     }
  32. };

This is the end of the string-related questions

Personal profile

I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages ​​such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.

my contact information

Mail