leetcode205-同构字符串

原题

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

如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。

示例1:

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

示例2:

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

示例3:

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

解法

思想

  1. 相同的字符要对应相同的字符,那么相同字符处于后位置的字符的第一次出现的位置就应该相同。
  2. 哈希表记录对应关系

代码

  1. indexOf (作者:hao-fei-hao)
class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] ch1 = s.toCharArray();
        char[] ch2 = t.toCharArray();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if(s.indexOf(ch1[i]) != t.indexOf(ch2[i])){
                return false;
            }
        }
        return true;
    }
}
  1. 哈希表
class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character,Character> map = new HashMap<>(); 
        Map<Character,Character> mapB = new HashMap<>(); 
        for(int i = 0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                if(t.charAt(i)!=map.get(s.charAt(i))) return false;
            }
            if(mapB.containsKey(t.charAt(i))){
                if(s.charAt(i)!=mapB.get(t.charAt(i))) return false;
            }
            map.put(s.charAt(i),t.charAt(i));
            mapB.put(t.charAt(i),s.charAt(i));
        }
        return true;
    }
}

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character,Character> 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;
                else map.put(s.charAt(i),t.charAt(i));
            }
        }
        return true;
    }
}
  1. 抽象一个模式字符串来匹配
func isIsomorphic(s string, t string) bool {
    return patternStr(s) == patternStr(t)
}

func patternStr(s string) string{
    letterCount := map[byte]int{}
    count := 1
    res := ""
    for _, c := range []byte(s){
        thisCount := letterCount[c]
        if thisCount == 0{
            letterCount[c] = count
            thisCount = count
        }
        res += strconv.Itoa(thisCount)
        count ++
    }
    return res
}

相似题

https://leetcode.cn/problems/word-pattern/description/

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode205-%e5%90%8c%e6%9e%84%e5%ad%97%e7%ac%a6%e4%b8%b2/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月20日
下一篇 2019年12月21日

相关推荐

  • leetcode450-删除二叉搜索树中的节点

    原题 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一…

    2020年1月16日
    090
  • 蓝桥杯试题-黑色星期五

    原题 资源限制 时间限制:1.0s 内存限制:512.0MB 问题描述  有些西方人比较迷信,如果某个月的13号正好是星期五,他们就会觉得不太吉利,用古人的说法,就是“诸事不宜”。…

    算法 2020年2月28日
    0120
  • leetcode155-最小栈

    原题 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() …

    算法 2019年12月11日
    0130
  • leetcode55-跳跃游戏

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例1: 输入: [2,3,1…

    算法 2020年2月9日
    080
  • leetcode112-路径总和

    原题 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:  给定如下二叉树,…

    算法 2020年1月12日
    0150
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04590
  • leetcode331-验证二叉树的前序序列化

    原题 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。 _9_ / \ 3 2…

    算法 2020年1月26日
    090
  • leetcode376-摆动序列

    原题 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如, [1,7,4,9,…

    算法 2020年2月18日
    0110
  • leetcode589-N叉树的前序遍历

    原题 给定一个 N 叉树,返回其节点值的前序遍历。 例如,给定一个 3叉树 : 返回其前序遍历: [1,3,5,6,2,4]。 说明: 递归法很简单,你可以使用迭代法完成此题吗? …

    2020年1月19日
    01030
  • leetcode13-罗马数字转整数

    原题 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2…

    算法 2020年4月25日
    090

发表回复

登录后才能评论