給定一個數組，求兩個字串長度總和的最大值，這兩個字串沒有相同的字符

本文的目的是實現一個程序，以最大化給定數組中沒有公共字元的一對字串的長度總和。根據定義，字串是字元的集合。

問題陳述

實作一個程序，以最大化給定數組中沒有公共字元的一對字串的長度總和。

範例 1

Let us consider the Input array: 
a[] = [“efgh”, “hat”, “fto”, “car”, “wxyz”, “fan”]

Output obtained: 8

說明

字串「abcd」和「wxyz」中沒有共同字元。結果，兩個字串相加的長度為 4 4，等於 8，是所有可行對中最長的長度。

範例 2

Let us consider the Input array: 
a[] = [“abc”, “cat”, “bat”, “hij”, “abcd”, “an”, "can"]

Output obtained: 7

說明

字串「abcd」和「hij」中沒有共同字元。結果，兩個字串相加的長度為 4 3，等於 8，是所有可行對中最長的長度。

範例 3

Let us consider the Input array: 
a[] = [“xyz”, “zip”, “lmno”, “lot”, “abcdx”, “yo”]

Output obtained: 9

說明

字串「abcdx」和「lmno」中沒有共同字元。結果，兩個字串相加的長度為 5 4，等於 9，是所有可行對中最長的長度。

範例 4

Let us consider the Input array: 
a[] = [“abc”, “coat”, “bat”, “hij”, “abcd”, “an”]

Output obtained: 7

說明

字串「coat」和「hij」中沒有共同字元。結果，兩個字串相加的長度為 4 3，等於 8，是所有可行對中最長的長度。

解決方案

為了最大化給定數組中沒有公共字元的一對字串的長度總和，我們採用以下方法。

解決此問題或找到最大化給定數組中沒有公共字元的一對字串的長度總和的方法如下。也就是說，處理上述問題的最直接的方法是建立字串陣列的每個潛在對，然後顯示所有可能的沒有公共字元的對的字串長度總和的最大值。

利用位元操作的概念，還可以改進上述策略。這裡的目標是在識別不共享公共字元且具有最長可能長度總和的字串對之前，將每個字串轉換為其等價的位元遮罩整數。

BitMasking 是我們目前的主題。位元遮罩到底是什麼？

我們首先要記住什麼是整數。整數只是串在一起的位元的集合。位元遮罩的概念是使用二進位形式以圖形方式表示數字。

簡單地說，「位元遮罩」就是一個可以指定任何內容的二進制數。

演算法

下面給出了實現程序以最大化給定數組中沒有公共字元的一對字串的長度總和的演算法。

• 第 1 步 - 開始

• 步驟 2 - 建立一個 memset() 函數以零初始化位元遮罩陣列。初始大小為 L 的位元遮罩，用於在字串 arr[] 陣列中記錄字串的位元或。

• 第 3 步 - 若要儲存回應，請將 maxLength 變數的值設為 0。

• 步驟 4 - 在利用變數 i 迭代範圍 [0, L] 的同時執行以下操作 -

• #第5 步 - 將bitmask[i] 的值定義為mask[i]|1(arr[i][j] - 'a') 並迭代範圍[ 0, S]，其中S是字串的大小。

• 第6 步 - 使用整數變數j 迭代範圍[0, i] 並將maxLength 的值設為arr[i].length() 的最大值如果bitmask[i]和bitmask[j]按位與結果不為0，則arr[j].length()。

• 第 7 步 - 最後列印所得的結果。

• 第 8 步 - 停止

#範例：C 程式

這是上述編寫的演算法的 C 程式實現，用於最大化給定數組中沒有公共字元的一對字串的長度總和

這是上述編寫的演算法的 C 程式實現，用於最大化給定數組中沒有公共字元的一對字串的長度總和

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 26
// Defining a function maxSumLength used to determine the longest combinedlength of two strings with no shared characters
int maxSumLength(char* arr[], int n){

   // Stores the bitmask of each string
   int bitmask[n];
   
   // Initialize the bitmask of each string to 0
   memset(bitmask, 0, sizeof(bitmask));
   
   // set the res to number 0
   int res = 0;
   
   // Now iterating this
   for (int i = 0; i < n; ++i) {
   
      // For every given elements 
      for (int j = 0; j < strlen(arr[i]); ++j) {
      
         // If the ith value of bitmask |= 1 then left shift that particular character - a
         bitmask[i] |= 1 << (arr[i][j] - 'a');
      }
      
      // Check for all the ith element, whether the ith and jth values of the
      // mask are not equal, if so add and also maximize those
      for (int j = 0; j < i; ++j) {
         if (!(bitmask[i] & bitmask[j])) {
            res = (res > strlen(arr[i]) + strlen(arr[j])) ? res : strlen(arr[i]) + strlen(arr[j]);
         }
      }
   }
   
   // the obtained maximum sum of the lengths of the strings obtained is returned
   return res;
}

int main(){
   char* arr[] = { "abcd", "def", "xyz" };
   int n = sizeof(arr) / sizeof(arr[0]);
   printf("%d", maxSumLength(arr, n));
   return 0;
}

輸出

7

結論

同樣，我們可以最大化給定數組中沒有公共字元的一對字串的長度總和。

本文解決了獲取程序以最大化給定數組中沒有公共字元的一對字串的長度總和的挑戰。

這裡提供了 C 程式碼以及最大化給定數組中沒有公共字元的一對字串的長度總和的演算法。

以上是給定一個數組，求兩個字串長度總和的最大值，這兩個字串沒有相同的字符的詳細內容。更多資訊請關注PHP中文網其他相關文章！