当前位置: 面试刷题>> 最小字符串 (经典算法题500道)


题目补充描述

题目

给定一个字符串数组 arr,其中每个字符串都是由小写字母组成。你的任务是找到这个数组中可以通过重新排列字母形成的字典序最小的字符串。如果数组中存在多个这样的字符串,则返回其中任意一个。

示例

输入: arr = ["banana", "app", "apple", "ann", "an"]
输出: "ann"
解释: 
"ann" 可以通过重新排列 "an" 中的字母得到。
"banana" 可以重新排列成 "aabnnn",但 "ann" 的字典序更小。
"app" 和 "apple" 都不是可以通过重新排列得到的最小字符串。

PHP 示例代码

function minLexicographicalString($arr) {
    // 使用自定义排序函数对字符串进行排序
    usort($arr, function($a, $b) {
        // 将字符串转化为字符数组并按字典序排序
        $sortedA = str_split($a);
        $sortedB = str_split($b);
        sort($sortedA);
        sort($sortedB);
        // 比较排序后的字符串
        return strcmp(implode('', $sortedA), implode('', $sortedB));
    });
    // 返回排序后数组的第一个元素
    return $arr[0];
}

$arr = ["banana", "app", "apple", "ann", "an"];
echo minLexicographicalString($arr);  // 输出: ann

Python 示例代码

def minLexicographicalString(arr):
    # 使用自定义排序函数对字符串进行排序
    arr.sort(key=lambda x: sorted(x))
    # 返回排序后数组的第一个元素
    return arr[0]

arr = ["banana", "app", "apple", "ann", "an"]
print(minLexicographicalString(arr))  # 输出: ann

JavaScript 示例代码

function minLexicographicalString(arr) {
    // 使用数组的 sort 方法和自定义排序函数
    arr.sort((a, b) => {
        // 将字符串转化为字符数组并按字典序排序
        const sortedA = [...a].sort();
        const sortedB = [...b].sort();
        // 比较排序后的字符串
        return sortedA.join('').localeCompare(sortedB.join(''));
    });
    // 返回排序后数组的第一个元素
    return arr[0];
}

const arr = ["banana", "app", "apple", "ann", "an"];
console.log(minLexicographicalString(arr));  // 输出: ann

// 码小课网站中有更多相关内容分享给大家学习

以上代码展示了如何在 PHP、Python 和 JavaScript 中实现寻找可以通过重新排列字母形成的字典序最小的字符串的算法。每段代码都通过自定义排序函数对字符串数组进行排序,排序的依据是字符串中字符的字典序排列结果。

推荐面试题