LeetCode 205. Isomorphic Strings

[quinnwencn]

Description

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true
Example 2:

Input: s = "foo", t = "bar"
Output: false
Example 3:

Input: s = "paper", t = "title"
Output: true

Constraints:

1 <= s.length <= 5 * 104
t.length == s.length
s and t consist of any valid ascii character.

[quinnwencn]

Analysis

When solving string-related problems, it is very common to map char to index, especially when the string is very long. In this problem, if we compare each char one by one, it will consume much time. But if we map the char to index, we only need to iterate the string once.

Solution written in Cpp

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }

        vector<int> indexS(256, -1);
        vector<int> indexT(256, -1);
        for (auto i = 0; i < s.length(); ++i) {
            if (indexS[s[i]] != indexT[t[i]]) {
                return false;
            }

            indexS[s[i]] = i;
            indexT[t[i]] = i;
        }

        return true;
    }
};

Solution written in Rust

In Rust, since we can not iterate string using indexs, we can only add a variable representing the index.

impl Solution {
    pub fn is_isomorphic(s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false;
        }

        let mut index_s = vec![-1; 256];
        let mut index_t = vec![-1; 256];
        let mut index = 0;
        let iter = s.chars().zip(t.chars());
        for (c1, c2) in iter {
            if index_s[c1 as usize] != index_t[c2 as usize] {
                return false;
            }

            index_s[c1 as usize] = index;
            index_t[c2 as usize] = index;
            index += 1;
        }

        true
    }
}