昨天没时间写刷题日记了，今天来补

lc383. 赎金信（EZ）

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote 和 magazine 由小写英文字母组成

哈希表经典题

这道题是出现的都是小写字母，所以可以用数组来代替哈希表，就是下面的 int[] hash = new int[26]

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (magazine.length() < ransomNote.length()) {
            return false;
        }
        int[] hash = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            hash[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            if (hash[ransomNote.charAt(i) - 'a'] == 0) {
                return false;
            }
            hash[ransomNote.charAt(i) - 'a']--;
        }
        return true;
    }
}

lc205. 同构字符串（EZ）

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"
输出：true

示例 2：

输入：s = "foo", t = "bar"
输出：false

示例 3：

输入：s = "paper", t = "title"
输出：true

提示：

  • 1 <= s.length <= 5 * 10^4
  • t.length == s.length
  • s 和 t 由任意有效的 ASCII 字符组成

写的第一个题解代码，个人感觉不太好，用了两个哈希表来存，时间表现也不太好，遂写了现在的代码，优化成了只需要一个哈希表，并且耗时也更短

没什么难度

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> hash = new HashMap<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char x = s.charAt(i), y = t.charAt(i);
            if (hash.containsKey(x)) {
                if (hash.get(x) != y) {
                    return false;
                }
            } else {
                if (hash.containsValue(y)) {
                    return false;
                }
                hash.put(x, y);
            }
        }
        return true;
    }
}

lc290. 单词规律（EZ）

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

提示:

  • 1 <= pattern.length <= 300
  • pattern 只包含小写英文字母
  • 1 <= s.length <= 3000
  • s 只包含小写英文字母和 ' '
  • s 不包含 任何前导或尾随对空格
  • s 中每个单词都被 单个空格 分隔

换汤不换药

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<String, Character> hash = new HashMap<>();
        int slen = s.length();
        int i = 0;
        for (int p = 0; p < pattern.length(); p++) {
            char ch = pattern.charAt(p);
            if (i >= slen) {
                return false;
            }
            int j = i;
            while (j < slen && s.charAt(j) != ' ') {
                j++;
            }
            String word = s.substring(i, j);
            if (hash.containsKey(word)) {
                if (hash.get(word) != ch) {
                    return false;
                }
            } else {
                if (hash.containsValue(ch)) {
                    return false;
                }
                hash.put(word, ch);
            }
            i = j + 1;
        }
        return i >= slen;
    }
}