返回介绍

solution / 2800-2899 / 2839.Check if Strings Can be Made Equal With Operations I / README_EN

发布于 2024-06-17 01:02:59 字数 4783 浏览 0 评论 0 收藏 0

2839. Check if Strings Can be Made Equal With Operations I

中文文档

Description

You are given two strings s1 and s2, both of length 4, consisting of lowercase English letters.

You can apply the following operation on any of the two strings any number of times:

  • Choose any two indices i and j such that j - i = 2, then swap the two characters at those indices in the string.

Return true_ if you can make the strings _s1_ and _s2_ equal, and _false_ otherwise_.

 

Example 1:

Input: s1 = "abcd", s2 = "cdab"
Output: true
Explanation: We can do the following operations on s1:
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbad".
- Choose the indices i = 1, j = 3. The resulting string is s1 = "cdab" = s2.

Example 2:

Input: s1 = "abcd", s2 = "dacb"
Output: false
Explanation: It is not possible to make the two strings equal.

 

Constraints:

  • s1.length == s2.length == 4
  • s1 and s2 consist only of lowercase English letters.

Solutions

Solution 1: Counting

We observe the operation in the problem, and find that if the parity of the two indices $i$ and $j$ of the string is the same, then their order can be changed by swapping.

Therefore, we can count the occurrence times of the characters at odd indices and even indices in the two strings. If the counting results of the two strings are the same, then we can make the two strings equal through the operation.

The time complexity is $O(n + |\Sigma|)$, and the space complexity is $O(|\Sigma|)$. Here, $n$ is the length of the string, and $\Sigma$ is the character set.

Similar problems:

class Solution:
  def canBeEqual(self, s1: str, s2: str) -> bool:
    return sorted(s1[::2]) == sorted(s2[::2]) and sorted(s1[1::2]) == sorted(
      s2[1::2]
    )
class Solution {
  public boolean canBeEqual(String s1, String s2) {
    int[][] cnt = new int[2][26];
    for (int i = 0; i < s1.length(); ++i) {
      ++cnt[i & 1][s1.charAt(i) - 'a'];
      --cnt[i & 1][s2.charAt(i) - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[0][i] != 0 || cnt[1][i] != 0) {
        return false;
      }
    }
    return true;
  }
}
class Solution {
public:
  bool canBeEqual(string s1, string s2) {
    vector<vector<int>> cnt(2, vector<int>(26, 0));
    for (int i = 0; i < s1.size(); ++i) {
      ++cnt[i & 1][s1[i] - 'a'];
      --cnt[i & 1][s2[i] - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[0][i] || cnt[1][i]) {
        return false;
      }
    }
    return true;
  }
};
func canBeEqual(s1 string, s2 string) bool {
  cnt := [2][26]int{}
  for i := 0; i < len(s1); i++ {
    cnt[i&1][s1[i]-'a']++
    cnt[i&1][s2[i]-'a']--
  }
  for i := 0; i < 26; i++ {
    if cnt[0][i] != 0 || cnt[1][i] != 0 {
      return false
    }
  }
  return true
}
function canBeEqual(s1: string, s2: string): boolean {
  const cnt: number[][] = Array.from({ length: 2 }, () => Array.from({ length: 26 }, () => 0));
  for (let i = 0; i < s1.length; ++i) {
    ++cnt[i & 1][s1.charCodeAt(i) - 97];
    --cnt[i & 1][s2.charCodeAt(i) - 97];
  }
  for (let i = 0; i < 26; ++i) {
    if (cnt[0][i] || cnt[1][i]) {
      return false;
    }
  }
  return true;
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文