Question

1417. 重新格式化字符串

English Version

题目描述

给你一个混合了数字和字母的字符串 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 仅由小写英文字母和/或数字组成。

解法

方法一：模拟

将字符串 $s$ 中的所有字符分成“数字”、“字母”两类，分别放入 $a$, $b$ 两个数组中。

比较 $a$, $b$ 两个数组的长度，若 $a$ 长度小于 $b$，则交换 $a$, $b$。接着判断两个数组长度差，若超过 $1$，则返回空字符串。

接着同时遍历两个数组，依次添加 $a$, $b$ 中对应字符到答案中。遍历结束，若 $a$ 长度大于 $b$，则添加 $a$ 的最后一个字符到答案中。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

class Solution:
  def reformat(self, s: str) -> str:
    a = [c for c in s if c.islower()]
    b = [c for c in s if c.isdigit()]
    if abs(len(a) - len(b)) > 1:
      return ''
    if len(a) < len(b):
      a, b = b, a
    ans = []
    for x, y in zip(a, b):
      ans.append(x + y)
    if len(a) > len(b):
      ans.append(a[-1])
    return ''.join(ans)

class Solution {
  public String reformat(String s) {
    StringBuilder a = new StringBuilder();
    StringBuilder b = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (Character.isDigit(c)) {
        a.append(c);
      } else {
        b.append(c);
      }
    }
    int m = a.length(), n = b.length();
    if (Math.abs(m - n) > 1) {
      return "";
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < Math.min(m, n); ++i) {
      if (m > n) {
        ans.append(a.charAt(i));
        ans.append(b.charAt(i));
      } else {
        ans.append(b.charAt(i));
        ans.append(a.charAt(i));
      }
    }
    if (m > n) {
      ans.append(a.charAt(m - 1));
    }
    if (m < n) {
      ans.append(b.charAt(n - 1));
    }
    return ans.toString();
  }
}

class Solution {
public:
  string reformat(string s) {
    string a = "", b = "";
    for (char c : s) {
      if (isdigit(c))
        a += c;
      else
        b += c;
    }
    int m = a.size(), n = b.size();
    if (abs(m - n) > 1) return "";
    string ans = "";
    for (int i = 0; i < min(m, n); ++i) {
      if (m > n) {
        ans += a[i];
        ans += b[i];
      } else {
        ans += b[i];
        ans += a[i];
      }
    }
    if (m > n) ans += a[m - 1];
    if (m < n) ans += b[n - 1];
    return ans;
  }
};

func reformat(s string) string {
  a := []byte{}
  b := []byte{}
  for _, c := range s {
    if unicode.IsLetter(c) {
      a = append(a, byte(c))
    } else {
      b = append(b, byte(c))
    }
  }
  if len(a) < len(b) {
    a, b = b, a
  }
  if len(a)-len(b) > 1 {
    return ""
  }
  var ans strings.Builder
  for i := range b {
    ans.WriteByte(a[i])
    ans.WriteByte(b[i])
  }
  if len(a) > len(b) {
    ans.WriteByte(a[len(a)-1])
  }
  return ans.String()
}