[LintCode] String Homomorphism

tanglijun 發布于2019-08-15 14:00 / 1642人閱讀

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.

Notice

You may assume both s and t have the same length.

Example

Given s = "egg", t = "add", return true.

Given s = "foo", t = "bar", return false.

Given s = "paper", t = "title", return true.

Solution

public class Solution {
    /*
     * @param s: a string
     * @param t: a string
     * @return: true if the characters in s can be replaced to get t or false
     */
    public boolean isIsomorphic(String s, String t) {
        //Map => (k, v) = (frequency, amount of chars)
        int[] map_S = new int[256];
        int[] map_T = new int[256];
        if (s == null || t == null || s.length() != t.length()) return false;
        for (int i = 0; i < s.length(); i++) {
            map_S[(int)s.charAt(i)]++; 
            map_T[(int)t.charAt(i)]++;
        }
        Map map = new HashMap<>();
        for (int i = 0; i < 256; i++) {
            if (!map.containsKey(map_S[i])) map.put(map_S[i], 1);
            else map.put(map_S[i], map.get(map_S[i])+1);
        }
        for (int i = 0; i < 256; i++) {
            if (!map.containsKey(map_T[i])) return false;
            else map.put(map_T[i], map.get(map_T[i])-1);
            if (map.get(map_T[i]) < 0) return false;
        }
        return true;
    }
}

GPU云服務器云服務器 Homomorphism LintCode LintCode134_LRU String

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

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

[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 評論0 收藏0
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 評論0 收藏0
[LintCode] Missing String

Problem Given two strings, you have to find the missing string. Example Given a string str1 = This is an exampleGiven another string str2 = is example Return [This, an] Solution public class Solution ...

IamDLY 2019-08-16 11:02 評論0 收藏0
[LintCode] String Compression

String Compression Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the compressed string w...

Cruise_Chan 2019-08-15 13:24 評論0 收藏0
[LintCode] Split String

Problem Give a string, you can choose to split the string after one character or two adjacent characters, and make the string to be composed of only one character or two characters. Output all possibl...

Riddler 2019-08-15 14:02 評論0 收藏0