问题:求最小字符串拼接序列

对于一个给定的字符串数组,请找到一种拼接顺序,使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。
不同于一般的排序,当元素A小于B时,A应该排在B前面。但是排列字符串的时候,字符串长度不一,所以使用以下策略:

  • if str1+str2 < str2+str1 ,则str1应排在str2前面
string findSmallest(vector<string> strs, int n) {
        for(int i=0;i<n-1;++i)
            for(int j=0;j<n-1-i;++j){
                if(strs[j]+strs[j+1]>strs[j+1]+strs[j]){
                    string t=strs[j];
                    strs[j]=strs[j+1];
                    strs[j+1]=t;
                }
            }
        string u;
        for(int i=0;i<n;++i)
            u+=strs[i];
        return u;
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔...
    叶总韩阅读 5,166评论 0 41
  • 第四章 字符串操作与正则表达式 1.mail()函数 bool mail (string to, string s...
    梁烨端木阅读 790评论 0 0
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,776评论 0 33
  • “你怕什么?” “怕蛇!” “怕老鼠!” “怕黑!” 不怕你笑话,我最怕打针。从小到现在,一直都是。也许在你眼里,...
    白范湘阅读 349评论 0 0
  • “妈妈,作业我肯定会写完的,但是你得让我多喘口气儿呀。你说我容易吗,作为一个小孩儿,我哪还有自己的童年了?你们大人...
    以琳阅读 304评论 0 0