[LeetCode] 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.

For example,
       
Given "egg", "add", return true.
        Given "foo", "bar", return false.
        Given "paper", "title", return true.

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


解题方法:
        该题意是判断两个字符串s和t是否是同构的。(注意字符不仅是字母)
        最简单的方法是通过计算每个字符出现的个数并且相应位置字母对应,但是两层循环肯定TLE。所以需要通过O(n)时间比较,采用的方法是:
        eg: "aba" <> "baa"  return false
        关键代码:nums[s[i]]=t[i]  numt[t[i]]=s[i] 再比较是否相同 
        nums['a']='b' numt['b']='a'  (第一次出现)
        nums['b']='a' numt['a']='b'  (第一次出现)
        nums['a']='b' <> t[2]='a'     (第二次出现)  return false
        该方法技巧性比较强,当然如果你使用C++的映射就非常容易实现了。

我的代码:

bool isIsomorphic(char* s, char* t) {
    int ls,lt;     //字符串长度
    int i,j;
    int nums[256]={0};
    int numt[256]={0};
    
    ls = strlen(s);
    lt = strlen(t);
    if(ls!=lt) return false;
    for(i=0; i<ls; i++) {
        //初值为0
        if(nums[s[i]]==0) {
            if(numt[t[i]]==0) {
                nums[s[i]] = t[i];
                numt[t[i]] = s[i];
            }
            else {
                return false;
            }
        }
        else {
            if(nums[s[i]]!=t[i]) {
                return false;
            }
        }
    }
    return true;
}


C++推荐代码:

        参考:http://www.cnblogs.com/easonliu/p/4465650.html
        题目很简单,也很容易想到方法,就是记录遍历s的每一个字母,并且记录s[i]到t[i]的映射,当发现与已有的映射不同时,说明无法同构,直接return false。但是这样只能保证从s到t的映射,不能保证从t到s的映射,所以交换s与t的位置再重来一遍上述的遍历就OK了。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.length() != t.length()) return false;
        map<char, char> mp;
        for (int i = 0; i < s.length(); ++i) {
            if (mp.find(s[i]) == mp.end()) mp[s[i]] = t[i];
            else if (mp[s[i]] != t[i]) return false;
        }
        mp.clear();
        for (int i = 0; i < s.length(); ++i) {
            if (mp.find(t[i]) == mp.end()) mp[t[i]] = s[i];
            else if (mp[t[i]] != s[i]) return false;
        }
        return true;
    }
};

(By:Eastmount 2015-9-21 凌晨1点半   http://blog.csdn.net/eastmount/)
目录
相关文章
|
3月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
109 1
|
5月前
|
Go 索引
【LeetCode 热题100】394:字符串解码(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 394:字符串解码。题目要求对编码字符串如 `k[encoded_string]` 进行解码,其中 `encoded_string` 需重复 `k` 次。文章提供了两种解法:使用栈模拟和递归 DFS,并附有 Go 语言实现代码。栈解法通过数字栈与字符串栈记录状态,适合迭代;递归解法则利用函数调用处理嵌套结构,代码更简洁。两者时间复杂度均为 O(n),但递归需注意栈深度问题。文章还总结了解题注意事项及适用场景,帮助读者更好地掌握字符串嵌套解析技巧。
124 6
|
11月前
|
存储 算法
Leetcode第三题(无重复字符的最长子串)
这篇文章介绍了解决LeetCode第三题“无重复字符的最长子串”的算法,使用滑动窗口技术来找出给定字符串中最长的不含重复字符的子串,并提供了详细的代码实现和解释。
495 0
Leetcode第三题(无重复字符的最长子串)
|
6月前
|
存储 机器学习/深度学习 缓存
🚀 力扣热题 394:字符串解码(详细解析)(Go语言版)
文章提供了两种解法:栈结构和递归解法。栈解法通过维护数字栈与字符串栈,依次处理 `[` 和 `]`,构造解码结果;递归解法则利用函数调用逐层解析嵌套结构。两者时间复杂度均为 $O(n)$,空间复杂度也为 $O(n)$。栈解法直观易懂,适合初学者;递归解法优雅简洁,适合处理深度嵌套规则。掌握这两种方法,可灵活应对类似问题,提升解题能力。
168 11
|
11月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
110 1
|
11月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
73 9
|
11月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
84 0
Leetcode第三十三题(搜索旋转排序数组)
|
11月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
168 0
|
11月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
121 0
|
11月前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
89 0