首页 > 代码库 > Isomorphic Strings
Isomorphic Strings
问题描述
给定两个字符串s和t,判断它们是否同构,是则返回true,否则返回false。
按照如下替换规则,如果字符串t能够通过替换字符串s中所有字符得到,则字符串s和字符串t同构。
- 替换时,必须保证字符串中各字符的出现顺序不变;
- 替换时,所有相同的字符只能被一个唯一字符替换;
- 替换时,不同的字符不能被同一个字符替换;
- 替换时,一个字符可以被它本身所替换。
注意:假定字符串s与字符串t长度相同。
输入示例
input1 | input2 | input3 |
"egg" | "foo" | "paper" |
"add" | "bar" | "title" |
输出示例
output1 | output2 | output3 |
true | false | true |
算法实现
- 注意到这里只是针对字符,所以利用ASCII码的关系在对应的字符的数位上存储该字符在字符串中上一次出现的位置。
- 判断字符串s与字符串t在对应下标位置i上的字符在该字符串中上次出现的位置是否相同。
- 如果不同,则说明字符串s与字符串t不同构,返回false。
- 如果相同,至少说明字符串s的子字符串s.substring(0, i)与字符串t的子字符串t.substring(0, i)同构,应该继续判断字符串s与字符串t在对应下个位置上的字符在该字符串中上次出现的位置是否相同,直至到最后一个字符。如果最后一个字符的判断结果仍然相同,则说明字符串s与字符串t同构,返回true。
1 public class Solution { 2 public boolean isIsomorphic(String s, String t) { 3 int[] m = new int[256]; 4 for(int i=0; i<s.length(); i++){ 5 if(m[s.charAt(i)] != m[t.charAt(i)+128]) return false; 6 m[s.charAt(i)] = m[t.charAt(i)+128] = i+1; 7 } 8 return true; 9 } 10 }
Isomorphic Strings
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。