[LeetCode] 205. Isomorphic Strings

graf 發布于2019-08-16 13:34 / 621人閱讀

Problem

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

Two strings 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
Note:
You may assume both s and t have the same length.

Solution Using HashMap

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

Using Array to replace Map

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] stmap = new int[256];
        int[] tsmap = new int[256];
        Arrays.fill(stmap, -1);
        Arrays.fill(tsmap, -1);
        for (int i = 0; i < s.length(); i++) {
            if (stmap[s.charAt(i)] != tsmap[t.charAt(i)]) return false;
            stmap[s.charAt(i)] = i;
            tsmap[t.charAt(i)] = i;
        }
        return true;
    }
}

云服務器 GPU云服務器 Isomorphic strings LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/71958.html

[Leetcode] Isomorphic Strings 同構字符串

摘要：最新更新思路和其他語言請訪問哈希表法復雜度時間空間思路用一個哈希表記錄字符串中字母到字符串中字母的映射關系，一個集合記錄已經映射過的字母。或者用兩個哈希表記錄雙向的映射關系。這里不能只用一個哈希表，因為要排除這種多對一的映射。 Isomorphic Strings 最新更新思路和其他語言請訪問：https://yanjia.me/zh/2018/11/... Given two st...

antz 2019-08-14 12:28 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[Leetcode] Word Pattern 單詞模式

摘要：哈希表法復雜度時間空間思路這題幾乎和一模一樣，不同的就是之前是字母映射字母，現在是字母映射字符串而已。 Word Pattern Given a pattern and a string str, find if str follows the same pattern. Examples: pattern = abba, str = dog cat cat dog should r...

wdzgege 2019-08-14 12:43 評論0 收藏0