LeetCode打卡第二天
给定两个字符串 s 和 t ,判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。
示例 1:
输入:s = "egg", t = "add"
输出:true
示例 2:
输入:s = "foo", t = "bar"
输出:false
示例 3:
输入:s = "paper", t = "title"
输出:true
这里很显然是做映射,就好比语文中的AABB、ABAC等四字成语一样,我最初想到的就是遍历字符串,然后按0123456等顺序组成,第一个字母出现即为1,
egg
则可表示为011
,而相同的字母可用Map
获取之前的计数的值
count
= 0,Map
存储字符,Stringbuilder
添加计算值char c = s.charAt(i)
StringBuilde
增加计数的count
,若map.get(c)
不为null,则表示当前字符已经存在,则添加该字符的值,若为null,map添加元素,且计数count++
,StringBuilde
添加计数值count
= 0,Map
存储字符,Stringbuilder
添加计算值char c = s.charAt(i)
StringBuilde
增加计数的count
,若map.get(c)
不为null,则表示当前字符已经存在,则添加该字符的值,若为null,map添加元素,且计数count++
,StringBuilde
添加计数值初始化两张哈希表,第一张哈希表 s2t 以 s中字符为键,映射至 t 的字符为值,第二张哈希表t2s 以 t 中字符为键,映射至 s 的字符为值
不断遍历字符,若产生冲突,说明无法进行同构
这里以示例2为例
输入:s = "foo", t = "bar"
第一轮
s2t(f,b)
t2s(b,f)
第二轮
s2t(o,a)
t2s(a,o)
第三轮
s2t(o,r)
因第二轮已经存在(o,a),产生冲突,返回false
t2s(b,f)
class Solution {
public boolean isIsomorphic(String s, String t) {
//若其中一个为空则返回false
if("" == s || "" == t){
return false;
}
return isIsomorphicTran(s).equals(isIsomorphicTran(t));
}
public String isIsomorphicTran(String s){
int n = s.length();
//存储字符和计数值
Map<Character, Integer> map = new HashMap<Character, Integer>(n);
StringBuilder sb = new StringBuilder();
int count = 0;
for(int i = 0; i < n; i++){
char c = s.charAt(i);
Integer j = map.get(c);
//若不为空,则添加已经存在的计数值
if(null != j){
sb.append(j);
}else{
//为空,则为新的字符,计数+1
count++;
map.put(c, count);
sb.append(count);
}
}
return sb.toString();
}
}
class Solution {
public boolean isIsomorphic(String s, String t) {
//初始化map
Map<Character, Character> s2t = new HashMap<Character, Character>();
Map<Character, Character> t2s = new HashMap<Character, Character>();
int len = s.length();
for (int i = 0; i < len; ++i) {
char x = s.charAt(i), y = t.charAt(i);
//如果产生冲突则返回false
if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
return false;
}
//添加元素进map
s2t.put(x, y);
t2s.put(y, x);
}
return true;
}
}
时间复杂度:遍历的次数为字符串的长度,所以复杂度为O(n)
空间复杂度:O(1)
时间复杂度:时间复杂度:O(n),其中 n 为字符串的长度。我们只需同时遍历一遍字符串 s和 t 即可
空间复杂度:O(∣Σ∣),其中 Σ 是字符串的字符集。哈希表存储字符的空间取决于字符串的字符集大小,最坏情况下每个字符均不相同,需要 O(∣Σ∣) 的空间。
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。 进阶: 如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
示例 1:
输入:s = "abc", t = "ahbgdc"
输出:true
示例 2:
输入:s = "axc", t = "ahbgdc"
输出:false
题目中可以得到的信息:为t的子序列,且顺序不能变,按照t的字符顺序排列
i
和j
,分别用于遍历字符串s
和t
i < s && j < t
,不能超过字符串长度s
的第i
个字符等于t
的某一个字符,则i++
,s
开始遍历第二个、第三个元素t
一直遍历直到结束i==n
,也就是s
字符串遍历完了,存在相等 class Solution {
public boolean isSubsequence(String s, String t) {
//获取字符长度
int n = s.length(), m = t.length();
//初始化遍历指针
int i = 0, j = 0;
//i 遍历对应 n , j -> m
while(i < n && j < m){
//s的第i个元素 == t的第j个元素,若相等,则s+1,s往后遍历
if(s.charAt(i) == t.charAt(j)){
i++;
}
// j往后遍历
j++;
}
//是否遍历完
return i == n;
}
}
时间复杂度:O(n+m),其中 n 为 s 的长度,m 为 t 的长度。每次无论是匹配成功还是失败,都有至少一个指针发生右移,两指针能够位移的总距离为 n+m。
空间复杂度:O(1)。