词典分类

Question

我正在做一个问题，上面写着“串联以产生词典最低的弦。”从比赛中。

以此字符串为例： jibw ji jp bw jibw

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

当我对此进行分类时，我会得到： bw ji jibw jibw jp.

这是否意味着这没有排序？如果是排序，“词典”分类是否考虑到将较短的字符串推向背面或其他东西？

我一直在阅读 词汇秩序 而且我看不到使用的任何点或方案，您有什么吗？

Answer 1

看来您正在寻找的是对这个问题的更好理解，所以让我清楚地表明。通常对字符串进行分类 是 词典分类。如果将字符串[JIBW，JI，JP，BW，JIBW]排序为词典顺序，则分类序列 是 BW，JI，JIBW，JIBW，JP]，这就是您得到的。因此，您的问题不是理解“词典”一词。您已经正确理解了它。

您的问题是您正在误读问题。这个问题不要求你 种类 字符串按词典顺序。 （如果确实如此，您通过排序得到的答案是正确的。）相反，它要求您生产 一 字符串，得到 串联 输入字符串以某种顺序（即，制作一个没有空间的字符串），因此所得的单字符串在词典上是最小的。

为了说明差异，请考虑通过串联排序序列和答案字符串来考虑您获得的字符串：

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

现在，当您比较这两个字符串时 - 请注意，您只是在比较两个14个字符的字符串，而不是两个字符串 - 您可以看到正确答案的确比您的答案要小于您的答案：您的答案以“ 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

我一直在这个Facebook黑客杯中使用F＃。在这场比赛中学到了很多东西。由于网络上F＃上的文档仍然很少见，因此我认为我不妨在这里分享一些。

此问题要求您根据自定义比较方法对字符串列表进行排序。这是我在f＃中的代码片段。

    let comparer (string1:string) (string2:string) =
         String.Compare(string1 + string2, string2 + string1)

    // Assume words is an array of strings that you read from the input
    // Do inplace sorting there
    Array.sortInPlaceWith comparer words
    // result contains the string for output
    let result = Array.fold (+) "" words

Answer 4

//使用此代码块打印阵列的词典分类字符，或者可以通过多种方式使用。

  #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);
        }
    }

Answer 5

您发布的示例表明，单纯的排序不会产生词典最低的字符串。对于给定的问题，您需要应用一些其他技巧来确定在哪个字符串之前（截至目前，我无法想到确切的方法）

实际输出不会违反词典最低词的条件。

Answer 6

Linux上的排序命令还进行词典分类，并以bw ji ji jibw jibw jp的顺序生成输出

Answer 7

检查这里发生的事情：

如果您只使用词典形式，您将获得BW JI JIBW JIBW JP，但是如果您通过令牌分析令牌，您会发现“ BWJIBW”（BW，JIBW）的词典比“ Bwjibw”低（BWJIBW”（BW，JI，JI，JI，JI，JI，JI，JI，JI，JI）这就是为什么答案是bw jibw jibw ji jp，因为首先，您应该附加bwjibwjibw，然后您可以加入JI和JP以获得最低的字符串。

Answer 8

一个仅涉及排序的简单技巧，它将适用于此问题，因为指定了最大字符串长度，将是将所有字符串添加到最大长度，并在字符串中的第一个字母。然后，您对填充的字符串进行排序，但输出原始的未加固的字符串。对于前。对于字符串长度2和输入B和BA，您将对BB和BA进行排序，这将为您提供BA和BB，因此您应该输出BAB。

Answer 9

如果您使用特殊的“占位符”字符添加，那么Prasun的技巧就可以使用，该角色可以加权以比字符串排序功能中的“ Z”大。结果将为您提供最低词典组合的顺序。

Answer 10

比赛已经结束，所以我发布了可能的解决方案，不是最有效的，而是一种方法

 #include <iostream>
 #include <fstream>
 #include <string>
    #include <algorithm>
    using namespace std;
   int main()
  {
ofstream myfile;
myfile.open("output.txt");
int numTestCases;
int numStrings;
string* ptr=NULL;
char*ptr2=NULL;
string tosort;
scanf("%d",&numTestCases);
for(int i=0;i<numTestCases;i++)
{
    scanf("%d",&numStrings);
    ptr=new string[numStrings];
    for(int i=0;i<numStrings;i++)
    {
        cin>>ptr[i];
    }
    sort(ptr,ptr+numStrings);
    for(int i=0;i<numStrings;i++)
    {
        next_permutation(ptr,ptr+numStrings);
    }
    tosort.clear();
    for(int i=0;i<numStrings;i++)
    {
        tosort.append(ptr[i]);
    }
    ptr2=&tosort[i];

    cout<<tosort<<endl;
    myfile<<tosort<<endl;   
    delete[]ptr;
}
return 0;
  }

我正在使用C ++中STL库中的算法，Prev_PerMuart功能简单地生成置换词典。