X

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.

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