LEETCODE 1417. Reformat The String 解题思路分析

题目大意：

重新格式化字符串

给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。

请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。

请你返回 重新格式化后 的字符串；如果无法按要求重新格式化，则返回一个 空字符串 。

示例 1：

输入：s = "a0b1c2"
输出："0a1b2c"
解释："0a1b2c" 中任意两个相邻字符的类型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。

示例 2：

输入：s = "leetcode"
输出：""
解释："leetcode" 中只有字母，所以无法满足重新格式化的条件。

示例 3：

输入：s = "1229857369"
输出：""
解释："1229857369" 中只有数字，所以无法满足重新格式化的条件。

示例 4：

输入：s = "covid2019"
输出："c2o0v1i9d"

示例 5：

输入：s = "ab123"
输出："1a2b3"

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母和/或数字组成。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1417

解题思路分析：

1. 先将字符串中的字符按照数字和字母分成两组，存放在两个list中
2. 如果两个list中的元素个数差大于1，说明无法按要求格式化，返回空
3. 我们从两个list中按顺序分别取出相同index下的字符，拼接起来加入返回结果。这里需要注意一点，如果字母数量多于数字个数，那么使用字母加数字的方式组合，最后将多出来的一个字母放在最后。反之如果数字数量多于字母，则要采用数字加字母的方式组合。最后多出的一个数字放在最后。另外如果数字与字母个数相同，怎么组合都可。

实现代码：

public String reformat(String s) {
    // 字符串中所有数字
    List<Character> listNums = new ArrayList<>();
    // 字符串中所有字母
    List<Character> listChars = new ArrayList<>();
    for(int i=0;i<s.length();i++){
        char c = s.charAt(i);
        if(c>='0'&&c<='9'){
            listNums.add(c);
        }else{
            listChars.add(c);
        }
    }
    if(Math.abs(listNums.size()-listChars.size())>1){
        return "";
    }
    StringBuilder sb = new StringBuilder();
    for(int i=0;i<Math.min(listNums.size(), listChars.size());i++){
        if(listNums.size()>listChars.size()){
            sb.append(listNums.get(i)).append(listChars.get(i));
        }else{
            sb.append(listChars.get(i)).append(listNums.get(i));
        }
    }
    if(listNums.size()>listChars.size()){
        sb.append(listNums.get(listNums.size()-1));
    }else if(listNums.size()<listChars.size()){
        sb.append(listChars.get(listChars.size()-1));
    }
    return sb.toString();
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 92.40% of Java online submissions for Reformat The String.

Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Reformat The String.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1417-reformat-the-string-解题思路分析/