词典编排

Question

我正在做一道题，题为“连接单词以生成字典顺序最低的字符串”。来自一场比赛。

以这个字符串为例：jibw ji jp bw jibw

实际的输出结果是：bw jibw jibw ji jp

当我对此进行排序时，我得到：bw ji jibw jibw jp。

这是否意味着这不是排序？如果是排序，“字典序”排序是否会考虑将较短的字符串推到后面或其他地方？

我在lexigographical order上做了一些阅读，我看不到任何使用它的点或场景，你有吗？

Answer 1

看起来你想要的是对这个问题更好的理解，所以让我把它说清楚。通常对字符串的排序是按字典排序。如果将字符串jibw、ji、jp、bw、jibw按字典顺序排序，则排序后的顺序为bw、ji、jibw、jibw、jp，这就是您得到的结果。所以你的问题不是理解“字典学”这个词；你已经正确地理解了它。

你的问题是你误解了问题。问题不会要求您按字典顺序对字符串进行排序。(如果是这样，您通过排序得到的答案将是正确的。)相反，它要求您生成一个字符串，该字符串是通过以某种顺序连接输入字符串而获得的(即，使一个字符串不带空格)，因此得到的单个字符串在字典顺序上是最小的。

为了说明不同之处，请考虑通过连接排序后的序列和答案字符串获得的字符串：

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

现在，当您比较这两个字符串时，您只是比较两个14个字符的字符串，而不是两个字符串序列，- you可以看到正确的答案在字典顺序上确实比您的答案小:您的答案以"bwjij“开头，而正确的答案以"bwjib”开头，并且按照字典顺序，"bwjib“在"bwjij”之前。

希望你现在能理解这个问题。这根本不是一个排序问题。(也就是说，对输入字符串进行排序不是问题。您可以对通过排列和连接输入字符串获得的所有可能的字符串进行排序；如果输入字符串的数量很少，这是解决问题的一种方法。)

Answer 2

您可以通过将word1 + word2与word2 + word1进行比较，将其转换为一个微不足道的排序问题。在Python中：

def cmp_concetanate(word1, word2):
    c1 = word1 + word2
    c2 = word2 + word1
    if c1 < c2:
        return -1
    elif c1 > c2:
        return 1
    else:
        return 0

将此比较函数与标准排序一起使用可以解决这个问题。

Answer 3

//使用这段代码打印按字典顺序排序的数组字符，或者可以通过多种方式使用它。

  #include<stdio.h>
  #include<conio.h>

  void combo(int,int,char[],char[],int*,int*,int*);

  void main()
  {
      char a[4]={'a','b','c'};
      char a1[10];
      int i=0,no=0;
      int l=0,j=0;
      combo(0,3,a,a1,&j,&l,&no);
      printf("%d",no);
      getch();
  }
  void combo(int ctr,int n,char a[],char a1[],int*j,int*l,int*no)
  {
      int i=0;
      if(ctr==n)
      {
        for(i=0;i<n;i++)
            printf("%c",a1[i]);
        printf("\n");
        (*no)++;
        (*j)++;
        if((*j)==n)
        { 
            *l=0;
             *j=0;
        }
        else
        *l=1;       
        getch();
      }
      else
        for(i=0;i<n;i++)
        {
        if(*l!=1)
            *j=i;
        a1[ctr]=a[*j];
        combo(ctr+1,n,a,a1,j,l,no);
        }
    }