LeetCodeDay08

242. 有效的字母异位词

描述

• 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

示例

• s = "anagram"，t = "nagaram"，返回 true
• s = "rat"，t = "car"，返回 false

注意

• 假定字符串只包含小写字母。

提升难度

• 输入的字符串包含 unicode 字符怎么办？你能能否调整你的解法来适应这种情况？
  • 将常量大小的vector转为能够自动扩容的unordered_map
  • 利用排序

思路

1. 字母异位词直观意思代表两个单词的组合成分相同，即各字符数量相同。中心思想是遍历，可以利用空间换时间，利用一个Map保存每个字母出现的次数，再去遍历另一个字符串，然后依次减1，最后出现此处全为0，则返回true。
2. 遍历的另一种思想，即排序。将两个字符串依次排序，然后一一遍历。更好的方法是排序后直接判断是否相等。

Tips

• String 类型的对象可以直接使用sort进行排序，不用额外转为vector。
• 遍历的两种优化思维，排序、空间换时间。

class Solution_242_01 {
 public:
  bool isAnagram(string s, string t) {
    vector<int> cnt(26);
    for (char val : s) {
      cnt[val - 'a']++;
    }
    for (char val : t) {
      cnt[val - 'a']--;
    }
    for (int val : cnt) {
      if (val != 0) return false;
    }
    return true;
  }
};

// 笨重的写法
class Solution_242_02 {
 public:
  bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    vector<char> v1(s.begin(), s.end());
    vector<char> v2(t.begin(), t.end());
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    auto iter1 = v1.begin(), iter2 = v2.begin();
    while (iter1 != v1.end()) {
      if (*iter1 != *iter2) return false;
      ++iter1;
      ++iter2;
    }
    return true;
  }
};
// 更优雅的写法
class Solution_242_03 {
 public:
  bool isAnagram(string s, string t) {
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    return s == t;
  }
};

---

125. 验证回文字符串

描述

• 给定一个字符串，确定它是否是回文，只考虑字母数字字符和忽略大小写。

示例

"A man, a plan, a canal: Panama" 是回文字符串。
"race a car" 不是回文字符串。

注意

• 你有考虑过这个字符串可能是空的吗？ 在面试中这是一个很好的问题。
• 针对此题目，我们将空字符串定义为有效的回文字符串。

思路

1. 两指针一头一尾往中间靠。

Tips

编码过程有点捉急，半天没有弄出来，主要是边界条件没有很好确定，在加上没有把判断的条件封装成函数，导致结构混乱，简单总结两点：

1. 要活用continue
2. 学会复用的地方封装，有库函数的利用库函数。
3. 先确定本体框架，在添砖加瓦。

class Solution_125 {
 public:
  bool isPalindrome(string s) {
    int start = 0, end = s.size() - 1;
    while (start < end) {
      if (!isalnum(s[start])) {
        start++;
        continue;
      }
      if (!isalnum(s[end])) {
        end--;
        continue;
      }
      if (tolower(s[start]) != tolower(s[end])) return false;
      start++;
      end--;
    }
    return true;
  }
};