给定一个数组，求两个字符串长度之和的最大值，这两个字符串没有相同的字符

本文的目的是实现一个程序，以最大化给定数组中没有公共字符的一对字符串的长度总和。根据定义，字符串是字符的集合。

问题陈述

实现一个程序，以最大化给定数组中没有公共字符的一对字符串的长度总和。

示例 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中文网其他相关文章！