기술나눔

알고리즘: 문자열 관련

2024-07-12

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

목차

주제 1: 가장 긴 공통 접두사

질문 2: 가장 긴 회문 부분 문자열

주제 3: 이진합

질문 4: 문자열 곱하기

주제 1:가장 긴 공통 접두사

문자열 배열에서 가장 긴 공통 접두어를 찾는 함수를 작성하세요.

공통 접두사가 없으면 빈 문자열을 반환합니다.""

예시 1:

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

예 2:

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

힌트:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i]영문 소문자로만 구성

해결 방법 1: 쌍별 비교

첫 번째 해결책은 쌍별 비교 전략입니다. 먼저 처음 두 문자열을 비교한 후 처음 두 문자열의 공통 접두사를 세 번째 문자열과 비교하여 처음 세 문자열의 공통 접두사를 구합니다.

코드는 아래와 같이 표시됩니다.

  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. };

해결 방법 2: 통합 비교

통합 비교는 모든 문자열의 동일한 위치를 한 번에 비교하여 다른 문자가 나타날 때까지 위치가 동일한지 확인하는 것을 의미합니다.

여기서는 out-of-bounds 상황이 발생하게 되는데, 이는 특정 문자열이 종료되었다는 의미이며, 그러면 비교가 종료될 수 있습니다.

코드는 아래와 같이 표시됩니다.

  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. };

주제 2:가장 긴 회문 부분 문자열

문자열을 줘s,켜다s가장 긴 회문 부분 문자열

예시 1:

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

예 2:

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

일반적인 무차별 열거 알고리즘은 i와 j라는 두 개의 포인터를 설정하고 i를 고정한 다음 j를 뒤로 이동합니다. 이때 i와 j 사이의 문자열이 회문 부분 문자열인지 여부를 확인해야 합니다. 그리고 i와 j 사이에 회문 부분 문자열이 있는지 판단하면 여기서의 시간 복잡도는 O(N^2)이고, 전체 문자열을 순회하는 데 사용되는 외부 i 레이어가 중첩되어 있으므로 전체 폭력 열거 시간 복잡도가 매우 높아 O(N^3)에 도달합니다. 최적화된 중심 확장 알고리즘을 살펴보겠습니다.

솔루션: 중심 확장 알고리즘

중심 확장 알고리즘은 다음과 같습니다.

①중심점 고정
②중심점에서 시작하여 양쪽으로 확장(홀수, 짝수 길이 모두 고려)

즉, 중심점 i는 매번 고정되고, 매번 i의 왼쪽과 오른쪽으로 확장되어 i를 순회하는 이 알고리즘의 시간 복잡도는 O(N)이 됩니다. 중첩된 방향은 i의 왼쪽과 오른쪽입니다. 확장하면 시간 복잡도도 O(N)이므로 결국 위에서 언급한 폭력적인 솔루션보다 훨씬 최적화된 O(N^2)입니다. .

주목해야 할 것은 중심 확장 알고리즘의 두 번째 점입니다. 홀수는 왼쪽 및 오른쪽 포인터를 i 위치에서 왼쪽 및 오른쪽으로 이동시키는 반면, 짝수는 필요하기 때문에 홀수와 짝수를 고려해야 합니다. 왼쪽은 i 위치에 있고 오른쪽은 i + 1 위치에 있는 다음 왼쪽과 오른쪽으로 이동합니다.

코드의 길이는 오른쪽 - 왼쪽 - 1입니다. 현재 왼쪽과 오른쪽이 동일한 요소를 가리키는 경우 left--, right++를 변경해야 하기 때문입니다. 동일하지 않으면 루프를 종료합니다. 이므로 회문 문자열보다 왼쪽과 오른쪽이 더 많습니다. 한 위치 이동했으므로 길이는 오른쪽 - 왼쪽 - 1에서 계산됩니다. 자세한 내용은 아래 그림을 참조하세요.

위 그림에서 볼 수 있듯이 왼쪽과 오른쪽은 루프를 종료하기 위해 현재 지점을 가리키므로 회문 부분 문자열 aa의 길이는 다음과 같습니다.
오른쪽 - 왼쪽 - 1 = 3 - 0 - 1 = 2

코드는 아래와 같이 표시됩니다.

  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. };

주제 3:이진합

두 개의 이진 문자열을 제공하십시오a그리고b, 합계를 이진 문자열로 반환합니다.

예시 1:

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

예 2:

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

고정밀 덧셈 계산, 시뮬레이션 연산 수행, 수직 계산 과정 시뮬레이션에 관한 질문입니다.

두 개의 포인터 cur1과 cur2를 각각 두 문자열을 가리키도록 설정한 다음 캐리를 나타내기 위해 변수 t를 설정해야 합니다.

코드는 아래와 같이 표시됩니다.

  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. };

주제 4:문자열 곱셈

문자열로 표현된 두 개의 음수가 아닌 정수가 주어지면num1그리고num2,반품num1그리고num2의 곱, 그들의 곱도 문자열 형태로 표현됩니다.

알아채다:내장된 BigInteger 라이브러리를 사용하거나 입력을 정수로 직접 변환할 수 없습니다.

예시 1:

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

예 2:

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

해결 방법 1: 수직 작업 시뮬레이션

수학에서는 곱셈란의 세로형을 생각하면 가장 쉬운 방법이다.

다음과 같이:

다음 456의 각 숫자에 위의 123을 곱하고 더하면 세 가지 세부 사항이 있다고 이해할 수 있습니다.

①고차 곱셈은 0으로 채워야 합니다., 738과 615를 더할 때 한 비트가 틀렸기 때문에 이는 738 + 6150으로 이해될 수 있습니다.
②프로세스 선두 0, 123×0의 상황이 발생할 수 있는데, 이 경우 답은 000이므로 처리가 필요하다.
③계산 결과의 순서에 주의하세요, 계산이 역순으로 이루어지고 곱셈은 마지막 숫자부터 계산되기 때문입니다.

하지만 이 방법은 코드를 작성하기가 쉽지 않습니다. 이를 최적화하려면 이 방법을 사용해야 합니다.

솔루션 2: 솔루션 1 최적화

캐리 없이 곱하고 더하면 마지막 단계에서 캐리가 처리됩니다.

즉, 아무리 곱해도 캐리가 발생하지 않으며 최종 덧셈 이후에 캐리가 수행됩니다.

마찬가지로 계산을 시작할 때는 먼저 순서를 반대로 하여 곱셈이 두 자릿수일 수 있으므로 대신 배열을 사용하여 저장할 수 있습니다.

순서가 반대이므로 123에 해당하는 첨자는 2,1,0이 되고, 456에 해당하는 첨자는 역시 2,1,0이 됩니다.

매우 유용한 규칙이 있습니다. i와 j에 첨자가 붙은 숫자를 곱하고 그 결과가 우연히 배열의 i + j번째 위치에 배치됩니다.

① 길이가 m + n - 1인 배열 tmp를 정의합니다. (m과 n은 곱해진 두 숫자의 길이에 해당합니다.)
곱해지는 두 숫자의 첨자는 각각 i와 j이며, 계산된 결과는 배열의 i + j번째 위치에 배치됩니다.
②최종 추가 후 캐리 처리가 필요합니다.
③선행 0 처리

코드는 아래와 같이 표시됩니다.

  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. };

이것으로 문자열 관련 질문이 종료됩니다.

개인 프로필

그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편