【时快讯】Go Java算法之同构字符串示例详解
目录
同构字符串方法一:哈希表(Java)方法一:哈希表(Go)同构字符串
给定两个字符串s和t,判断它们是否是同构的。
如果s中的字符可以按某种映射关系替换得到t,那么这两个字符串是同构的。
(相关资料图)
每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。
示例 1:示例 2:输入:s = "egg", t = "add"
输出:true
示例 3:输入:s = "foo", t = "bar"
输出:false
输入:s = "paper", t = "title"
输出:true
提示:
1 <= s.length <= 5 * 104
t.length == s.length
s和t由任意有效的 ASCII 字符组成
方法一:哈希表(Java)
此题需要我们判断 s 和 t 每个位置上的字符是否都一一对应,即 s 的任意一个字符被 t 中唯一的字符对应,同时 t 的任意一个字符被 s 中唯一的字符对应。这也被称为「双射」的关系。
以示例 2 为例,t 中的字符 a 和 r 虽然有唯一的映射 o,但对于 s 中的字符 o 来说其存在两个映射 {a,r},故不满足条件。
因此,我们维护两张哈希表,第一张哈希表 s2t 以 s 中字符为键,映射至 t 的字符为值,第二张哈希表 t2s 以 t 中字符为键,映射至 s 的字符为值。
class Solution { public boolean isIsomorphic(String s, String t) { Maps2t = new HashMap (); Map t2s = new HashMap (); int len = s.length(); for (int i = 0; i < len; ++i) { char x = s.charAt(i), y = t.charAt(i); if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) { return false; } s2t.put(x, y); t2s.put(y, x); } return true; } }
时间复杂度:O(N)
空间复杂度:O(1)
方法一:哈希表(Go)
具体的方法思路已经在上文中表述,具体详情请看上文内容。
方法思路:
定义两个map容器用于存储两个字符串的映射关系map_s、map_tmap_s:以 s 中字符为键,映射至 t 的字符为值map_t: 以 t 中字符为键,映射至 s 的字符为值遍历字符串(两个字符串长度相等同时遍历)不断更新两张哈希表,如果出现冲突时说明两个字符串无法构成同构,返回 false。冲突定义:即当前下标 index 对应的字符 map_s[index] 已经存在映射且不为 t[index] 或当前下标 index 对应的字符map_t[index] 已经存在映射且不为 s[index]也就是代码中的if判断条件func isIsomorphic(s, t string) bool { s2t := map[byte]byte{} t2s := map[byte]byte{} for i := range s { x, y := s[i], t[i] if s2t[x] > 0 && s2t[x] != y || t2s[y] > 0 && t2s[y] != x { return false } s2t[x] = y t2s[y] = x } return true }
时间复杂度:O(N)
空间复杂度:O(1)
以上就是Go Java算法之同构字符串示例详解的详细内容,更多关于Go Java算法同构字符串的资料请关注脚本之家其它相关文章!
X 关闭
X 关闭
- 1亚马逊开始大规模推广掌纹支付技术 顾客可使用“挥手付”结账
- 2现代和起亚上半年出口20万辆新能源汽车同比增长30.6%
- 3如何让居民5分钟使用到各种设施?沙特“线性城市”来了
- 4AMD实现连续8个季度的增长 季度营收首次突破60亿美元利润更是翻倍
- 5转转集团发布2022年二季度手机行情报告:二手市场“飘香”
- 6充电宝100Wh等于多少毫安?铁路旅客禁止、限制携带和托运物品目录
- 7好消息!京东与腾讯续签三年战略合作协议 加强技术创新与供应链服务
- 8名创优品拟通过香港IPO全球发售4100万股 全球发售所得款项有什么用处?
- 9亚马逊云科技成立量子网络中心致力解决量子计算领域的挑战
- 10京东绿色建材线上平台上线 新增用户70%来自下沉市场