美文网首页
问题:求最小字符串拼接序列

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

作者: 熊白白 | 来源:发表于2017-07-06 12:27 被阅读9次

    对于一个给定的字符串数组,请找到一种拼接顺序,使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。
    不同于一般的排序,当元素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;
        }
    

    相关文章

      网友评论

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

          本文链接:https://www.haomeiwen.com/subject/gfjhhxtx.html