Python程序重新排列字符串，以使所有相同字符相距d

  • Z时代
  • 2024-01-10
  • 分类：综合

给定一个非空字符串str和一个整数k，请重新排列该字符串，以使相同字符之间的距离至少为k。

所有输入字符串均以小写字母给出。如果无法重新排列字符串，则返回一个空字符串“”。

范例1：

str = “nhooo”, k = 3
Answer: “tiotiotalnprsu”

相同的字符至少要相距3个字符。

str = "aabbcc", k = 3
Answer: "abcabc"
The same characters are at least 3 character distance apart.

例子2

str = "aaabc", k = 3
Answer: ""
无法重新排列字符串。

范例3：

str = "aaadbbcc", k = 2
Answer: "abacabcd"
Another possible answer is: "abcabcda"
The same characters are at least 2 character distance apart.

示例

MAX = 128
# A structure to store a character 'char' and its frequency 'freq'
# in input string
class charFreq(object):
   def __init__(self,char,freq):
      self.c = char
      self.f = freq
# A utility function to swap two charFreq items.
def swap(x, y):
   return y, x
# A utility function
def toList(string):
   t = []
   for x in string:
      t.append(x)
   return t
# A utility function
def toString(l):
   return ''.join(l)
# A utility function to maxheapify the node freq[i] of a heap stored in freq[]
def maxHeapify(freq, i, heap_size):
   l = i*2 + 1
   r = i*2 + 2
   largest = i
   if l < heap_size and freq[l].f > freq[i].f:
      largest = l
   if r < heap_size and freq[r].f > freq[largest].f:
      largest = r
   if largest != i:
      freq[i], freq[largest] = swap(freq[i], freq[largest])
      maxHeapify(freq, largest, heap_size)
# A utility function to convert the array freq[] to a max heap
def buildHeap(freq, n):
   i = (n - 1)//2
   while i >= 0:
      maxHeapify(freq, i, n)
      i-=1
# A utility function to remove the max item or root from max heap
def extractMax(freq, heap_size):
   root = freq[0]
   if heap_size > 1:
      freq[0] = freq[heap_size-1]
      maxHeapify(freq, 0, heap_size-1)
return root
# The main function that rearranges input string 'str' such that
# two same characters become d distance away
def rearrange(string, d):
   # Find length of input string
   n = len(string)
   # Create an array to store all characters and their
   # frequencies in str[]
   freq = []
   for x in range(MAX):
      freq.append(charFreq(0,0))
   m = 0
   # Traverse the input string and store frequencies of all
   # characters in freq[] array.
   for i in range(n):
      x = ord(string[i])
      # If this character has occurred first time, increment m
      if freq[x].c == 0:
         freq[x].c = chr(x)
         m+=1
      freq[x].f+=1
      string[i] = '\0'
   # Build a max heap of all characters
   buildHeap(freq, MAX)
   # Now one by one extract all distinct characters from max heap
   # and put them back in str[] with the d distance constraint
   for i in range(m):
      x = extractMax(freq, MAX-i)
      # Find the first available position in str[]
      p = i
      while string[p] != '\0':
         p+=1
      # Fill x.c at p, p+d, p+2d, .. p+(f-1)d
      for k in range(x.f):
         # If the index goes beyond size, then string cannot
         # be rearranged.
         if p + d*k >= n:
            print ("无法重新排列字符串。")
         return
      string[p + d*k] = x.c
   return toString(string)
string = "nhooo"
print (rearrange(toList(string), 3) )

结果

tiotiotalnprsu

以上是 Python程序重新排列字符串，以使所有相同字符相距d 的全部内容， 来源链接： utcz.com/z/353452.html

回到顶部