dsal 字符串最小词典排列，它包含另一个字符串的所有子字符串

字符串最小词典排列，它包含另一个字符串的所有子字符串

原文：https://www.geeksforgeeks.org/lexicographically-smallest-permutation-of-a-string-that-contains-all-substrings-of-another-string/

给定两个字符串A和B，任务是从字典上找到字符串B的最小排列，以使其包含字符串A中的每个子字符串作为其子字符串。如果无法进行有效的排列，请打印-1。

示例：

输入：A = "aa", B = "ababab"

输出：aaabbb

说明：

A的所有可能子串是'a', 'a', 'aa'。

将字符串B重新排列为"aaabb"。

现在，在字典上，"aaabb"是B的最小排列，其中包含A的所有子串。

输入：A = "aaa", B = "ramialsadaka"

输出：aaaaadiklmrs

说明：

A的所有可能子串是'a', 'a', 'aaa'。

将字符串B重新排列为"aaaaadiklmrs"。

现在，"aaaaadiklmrs"是B在字典上的最小排列，其中包含A的所有子串。

朴素的方法：最简单的方法是生成字符串B的所有可能排列，然后从所有这些排列中，从字典上找到包含所有子串的最小排列A的组成。

时间复杂度：O(N!)。

辅助空间：O(1)。

有效方法：为优化上述方法，主要观察结果是，包含A所有子字符串的最小字符串是字符串A本身。因此，要对字符串B重新排序并包含A的所有子字符串，它必须包含A作为子字符串。仅当字符串B中每个字符的频率大于或等于A中的频率时，重新排序的字符串B才能包含A作为其子字符串。步骤如下：

计算数组freq[]中字符串B中每个字符的频率，然后从中减去字符串A中相应字符的频率。
为了按字典顺序生成最小的字符串，请初始化一个空字符串res，然后将其追加，其值小于字符串A的第一个字符的所有剩余字符。
在添加等于第一个字符A的所有字符之前，请检查是否存在小于字符串A中第一个字符的字符。如果是这样，则将A附加到第一个结果，然后将所有其余字符都等于A的第一个字符，以使重新排序的字符串在字典上最小。
否则，附加所有剩余的A[0]，然后附加A。
最后，将其余字符附加到结果中。
完成上述步骤后，打印字符串res。

下面是上述方法的实现：

C++

// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to reorder the string B
// to contain all the substrings of A
string reorderString(string A, string B)
{
    // Find length of strings
    int size_a = A.length();
    int size_b = B.length();

    // Initialize array to count the
    // frequencies of the character
    int freq[300] = { 0 };

    // Counting frequencies of
    // character in B
    for (int i = 0; i < size_b; i++)
        freq[B[i]]++;

    // Find remaining character in B
    for (int i = 0; i < size_a; i++)
        freq[A[i]]--;

    for (int j = 'a'; j <= 'z'; j++) {
        if (freq[j] < 0)
            return "-1";
    }

    // Declare the reordered string
    string answer;

    for (int j = 'a'; j < A[0]; j++)

        // Loop until freq[j] > 0
        while (freq[j] > 0) {
            answer.push_back(j);

            // Decrement the value
            // from freq array
            freq[j]--;
        }

    int first = A[0];

    for (int j = 0; j < size_a; j++) {

        // Check if A[j] > A[0]
        if (A[j] > A[0])
            break;

        // Check if A[j] < A[0]
        if (A[j] < A[0]) {
            answer += A;
            A.clear();
            break;
        }
    }

    // Append the remaining characters
    // to the end of the result
    while (freq[first] > 0) {
        answer.push_back(first);
        --freq[first];
    }

    answer += A;

    for (int j = 'a'; j <= 'z'; j++)

        // Push all the values from
        // frequency array in the answer
        while (freq[j]--)
            answer.push_back(j);

    // Return the answer
    return answer;
}

// Driver Code
int main()
{
    // Given strings A and B
    string A = "aa";
    string B = "ababab";

    // Function Call
    cout << reorderString(A, B);

    return 0;
}

Java

// Java program for 
// the above approach
class GFG{

// Function to reorder the String B
// to contain all the subStrings of A
static String reorderString(char []A, 
                            char []B)
{
  // Find length of Strings
  int size_a = A.length;
  int size_b = B.length;

  // Initialize array to count the
  // frequencies of the character
  int freq[] = new int[300];

  // Counting frequencies of
  // character in B
  for (int i = 0; i < size_b; i++)
    freq[B[i]]++;

  // Find remaining character in B
  for (int i = 0; i < size_a; i++)
    freq[A[i]]--;

  for (int j = 'a'; j <= 'z'; j++) 
  {
    if (freq[j] < 0)
      return "-1";
  }

  // Declare the reordered String
  String answer = "";

  for (int j = 'a'; j < A[0]; j++)

    // Loop until freq[j] > 0
    while (freq[j] > 0) 
    {
      answer+=j;

      // Decrement the value
      // from freq array
      freq[j]--;
    }

  int first = A[0];

  for (int j = 0; j < size_a; j++) 
  {
    // Check if A[j] > A[0]
    if (A[j] > A[0])
      break;

    // Check if A[j] < A[0]
    if (A[j] < A[0]) 
    {
      answer += String.valueOf(A);
      A = new char[A.length];
      break;
    }
  }

  // Append the remaining characters
  // to the end of the result
  while (freq[first] > 0) 
  {
    answer += String.valueOf((char)first);
    --freq[first];
  }

  answer += String.valueOf(A);

  for (int j = 'a'; j <= 'z'; j++)

    // Push all the values from
    // frequency array in the answer
    while (freq[j]-- > 0)
      answer += ((char)j);

  // Return the answer
  return answer;
}

// Driver Code
public static void main(String[] args)
{
  // Given Strings A and B
  String A = "aa";
  String B = "ababab";

  // Function Call
  System.out.print(reorderString(A.toCharArray(), 
                                 B.toCharArray()));
}
}

// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach

# Function to reorder the B
# to contain all the substrings of A
def reorderString(A, B):

    # Find length of strings
    size_a = len(A)
    size_b = len(B)

    # Initialize array to count the
    # frequencies of the character
    freq = [0] * 300

    # Counting frequencies of
    # character in B
    for i in range(size_b):
        freq[ord(B[i])] += 1

    # Find remaining character in B
    for i in range(size_a):
        freq[ord(A[i])] -= 1

    for j in range(ord('a'), ord('z') + 1):
        if (freq[j] < 0):
            return "-1"

    # Declare the reordered string
    answer = []

    for j in range(ord('a'), ord(A[0])):

        # Loop until freq[j] > 0
        while (freq[j] > 0):
            answer.append(j)

            # Decrement the value
            # from freq array
            freq[j] -= 1

    first = A[0]

    for j in range(size_a):

        # Check if A[j] > A[0]
        if (A[j] > A[0]):
            break

        # Check if A[j] < A[0]
        if (A[j] < A[0]):
            answer += A
            A = ""
            break

    # Append the remaining characters
    # to the end of the result
    while (freq[ord(first)] > 0):
        answer.append(first)
        freq[ord(first)] -= 1

    answer += A

    for j in range(ord('a'), ord('z') + 1):

        # Push all the values from
        # frequency array in the answer
        while (freq[j]):
            answer.append(chr(j))
            freq[j] -= 1

    # Return the answer
    return "".join(answer)

# Driver Code
if __name__ == '__main__':

    # Given strings A and B
    A = "aa"
    B = "ababab"

    # Function call
    print(reorderString(A, B))

# This code is contributed by mohit kumar 29

C

// C# program for 
// the above approach
using System;
class GFG{

// Function to reorder the String B
// to contain all the subStrings of A
static String reorderString(char []A, 
                            char []B)
{
  // Find length of Strings
  int size_a = A.Length;
  int size_b = B.Length;

  // Initialize array to count the
  // frequencies of the character
  int []freq = new int[300];

  // Counting frequencies of
  // character in B
  for (int i = 0; i < size_b; i++)
    freq[B[i]]++;

  // Find remaining character in B
  for (int i = 0; i < size_a; i++)
    freq[A[i]]--;

  for (int j = 'a'; j <= 'z'; j++) 
  {
    if (freq[j] < 0)
      return "-1";
  }

  // Declare the reordered String
  String answer = "";

  for (int j = 'a'; j < A[0]; j++)

    // Loop until freq[j] > 0
    while (freq[j] > 0) 
    {
      answer+=j;

      // Decrement the value
      // from freq array
      freq[j]--;
    }

  int first = A[0];

  for (int j = 0; j < size_a; j++) 
  {
    // Check if A[j] > A[0]
    if (A[j] > A[0])
      break;

    // Check if A[j] < A[0]
    if (A[j] < A[0]) 
    {
      answer += String.Join("", A);
      A = new char[A.Length];
      break;
    }
  }

  // Append the remaining characters
  // to the end of the result
  while (freq[first] > 0) 
  {
    answer += String.Join("", (char)first);
    --freq[first];
  }

  answer += String.Join("", A);

  for (int j = 'a'; j <= 'z'; j++)

    // Push all the values from
    // frequency array in the answer
    while (freq[j]-- > 0)
      answer += ((char)j);

  // Return the answer
  return answer;
}

// Driver Code
public static void Main(String[] args)
{
  // Given Strings A and B
  String A = "aa";
  String B = "ababab";

  // Function Call
  Console.Write(reorderString(A.ToCharArray(), 
                              B.ToCharArray()));
}
}

// This code is contributed by Rajput-Ji

输出：

aaabbb

时间复杂度：O(n)。

辅助空间：O(1)。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/36417.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-31》

分类

最近更新

dsal 字符串最小词典排列，它包含另一个字符串的所有子字符串

字符串最小词典排列，它包含另一个字符串的所有子字符串

C++

Java

Python3

C

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-31》

dsal 字符串最小词典排列，它包含另一个字符串的所有子字符串

字符串最小词典排列，它包含另一个字符串的所有子字符串

C++

Java

Python3

C

留言

联系客服

dsal 查看更多书籍