C++实现LeetCode(205.同构字符串)

[LeetCode] 205. Isomorphic Strings 同构字符串

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.

这道题让我们求同构字符串，就是说原字符串中的每个字符可由另外一个字符替代，可以被其本身替代，相同的字符一定要被同一个字符替代，且一个字符不能被多个字符替代，即不能出现一对多的映射。根据一对一映射的特点，需要用两个 HashMap 分别来记录原字符串和目标字符串中字符出现情况，由于 ASCII 码只有 256 个字符，所以可以用一个 256 大小的数组来代替 HashMap，并初始化为0，遍历原字符串，分别从源字符串和目标字符串取出一个字符，然后分别在两个数组中查找其值，若不相等，则返回 false，若相等，将其值更新为 i + 1，因为默认的值是0，所以更新值为 i + 1，这样当 i=0 时，则映射为1，如果不加1的话，那么就无法区分是否更新了，代码如下：

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (m1[s[i]] != m2[t[i]]) return false;
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        return true;
    }
};

到此这篇关于C++实现LeetCode(205.同构字符串)的文章就介绍到这了,更多相关C++实现同构字符串内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java实现LeetCode（螺旋矩阵）

    LeetCode54. 螺旋矩阵 java实现 题目 难度 中 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素. 示例 1: 输入:  [   [ 1, 2, 3 ],   [ 4, 5, 6 ],   [ 7, 8, 9 ]  ]  输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入:  [    [1, 2, 3, 4],    [5, 6, 7, 8],    [9,10,11,12]  ] 输出: [1,2,3,4,8

  • C++实现leetcode(3.最长无重复字符的子串)

    [LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", wit

  • Java实现LeetCode（两数之和）

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

  • C++实现LeetCode(2.两个数字相加)

    [LeetCode] 2. Add Two Numbers 两个数字相加 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked

  • C++实现LeetCode(两个有序数组的中位数)

    [LeetCode] 4. Median of Two Sorted Arrays 两个有序数组的中位数 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and 

  • C++实现LeetCode(205.同构字符串)

    [LeetCode] 205. Isomorphic Strings 同构字符串 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 w

  • C++实现LeetCode(87.搅乱字符串)

    [LeetCode] 87. Scramble String 搅乱字符串 Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great":     great /    \ gr    eat / \    /  \

  • C++实现LeetCode(151.翻转字符串中的单词)

    [LeetCode] 151.Reverse Words in a String 翻转字符串中的单词 Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the". Update (2015-02-12): For C programmers: Try to solve it in-p

  • C++实现LeetCode(557.翻转字符串中的单词之三)

    [LeetCode] 557.Reverse Words in a String III 翻转字符串中的单词之三 Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1: Input: "Let's take LeetCode conte

  • C++实现LeetCode(186.翻转字符串中的单词之二)

    [LeetCode] 186. Reverse Words in a String II 翻转字符串中的单词之二 Given an input string , reverse the string word by word.  Example: Input:  ["t","h","e"," ","s","k","y"," ","i&qu

  • Go Java算法之同构字符串示例详解

    目录 同构字符串 方法一:哈希表(Java) 方法一:哈希表(Go) 同构字符串 给定两个字符串 s 和 t ,判断它们是否是同构的. 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的. 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序.不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身. 示例 1: 输入:s = "egg", t = "add" 输出:true 示例 2: 输入:s = &

  • JavaScript前端学算法题解LeetCode最大重复子字符串

    JavaScript前端学算法题解LeetCode最大重复子字符串

    目录 最大重复子字符串 解题思路 知识点 这是LeetCode的第1668题:最大重复子字符串 最大重复子字符串 给你一个字符串 sequence ,如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串,那么单词 word 的 重复值为 k .单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值.如果 word 不是 sequence 的子串,那么重复值 k 为 0 .给你一个字符串 sequence 和 word ,请你返回

  • C C++算法题解LeetCode1408数组中的字符串匹配

    C C++算法题解LeetCode1408数组中的字符串匹配

    目录 题目描述 整理题意 解题思路分析 优化 具体实现 复杂度分析 代码实现 暴力 暴力 + 优化 KMP 总结 题目描述 题目链接:1408. 数组中的字符串匹配 给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词.请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词. 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串. 提示: 示例 1: 输入:wo

  • python 输入字符串生成所有有效的IP地址(LeetCode 93号题)

    这题的官方难度是Medium,点赞1296,反对505,通过率35.4%.从各项指标来说看起来有些中规中矩,实际上也的确如此.这道题的解法和立意都有些显得新意不足,但总体来说题目的质量还是可以的,值得一做. 题意 给定一个由数字组成的字符串,我们希望通过这个字符串得到所有有效ip地址的组合.对于一个有效的ip地址而言,它应该有4个数字组成,每一个数字的范围在0到255之间. 一个字符串可能可以转化成多个ip地址,我们需要存储下来所有可以成立的情况. 样例 Input: "25525511135&

  • 利用golang的字符串解决leetcode翻转字符串里的单词

    利用golang的字符串解决leetcode翻转字符串里的单词

    题目 给定一个字符串,逐个翻转字符串中的每个单词. 示例 1: 输入: "the sky is blue" 输出: "blue is sky the" 示例 2: 输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括. 示例 3: 输入: "a good example" 输出: "exampl

随机推荐