我在试着理解这个代码块,我在课堂上看到过,但我还是不明白。
我知道map是什么和如何工作的,它是一个键对值对象,在这个例子中,我只是不明白发生了什么,我看到我们有一个char和int,但我不明白他们在这个例子中是如何交互的。
class Solution {
public:
bool isIsomorphic(string s, string t) {
map<char, int> mapS;
map<char, int> mapT;
for(int i = 0; i < s.length(); i++)
{
if(mapS[s[i]] != mapT[t[i]]) return false;
mapS[s[i]] = i+1;
mapT[t[i]] = i+1;
}
return true;
}
};
我试着打印出每个for的结果,我得到了0和1(不是二进制意义上的)。我还知道我们在'i'+1处取一个字符并将其放置在maps索引中。我遗漏了什么?
谢谢!
抱歉,我还是不习惯在这里提出好的问题。
我试图首先理解解决方案,所以,就像有人建议的那样,我将用我的推理来解决它。
首先,我们启动两个贴图(mapS和mapT)。
第二步,迭代字符串s的长度(我想我们可以假设字符串t的长度是相同的,这一点还不清楚)。
我们检查s [i]处的字符是否等于t [i],并且它也必须存在于Map中(这就是我的问题所在)。
我把那条线当作向前看的线,并把它加到Map上。
如果没有问题,我们还会回来。
现在,如果我错了,请原谅,但是根据文档,我们不应该比较这里的键吗?或者我完全错过了一些东西。
另外,有人提到我是否理解同构。我不完全理解。我有一个大概的想法。
2条答案
按热度按时间6za6bjd01#
首先,我将检查一下你提供的解释。
首先,我们启动两个贴图(mapS和mapT)。
教育性地,我们 * 初始化 * 两个Map。
第二步,迭代字符串s的长度(我想我们可以假设字符串t的长度是相同的,这一点还不清楚)。
为了解决这个问题,我们可以假设
t
至少和s
一样长。我们检查s [i]处的字符是否等于t [i],
不,那是
s[i] == t[i]
.而这也必须存在于Map中。(这就是它对我来说分崩离析的地方)
不,如果我们没有在
mapS
中存储s[i]
的值,mapS[s[i]]
就是0。下面是
if
条件的实际作用:mapS
中查找s[i]
,返回一些int
--或者是我们最近为键s[i]
存储的int
,或者是0,如果我们从未为键s[i]
存储过int
。mapT
中查找t[i]
,返回一些int
--或者是我们最近为键t[i]
存储的int
,或者是0,如果我们从未为键t[i]
存储过int
。int
不同,则函数提前返回值false
。我把那条线当作向前看的线,并把它加到Map上。
它不会向前看,向前看的内容类似于
s[i+1]
或t[i+1]
,它确实在两个Map中都存储了i+1
,但它不会"向前看"。如果没有问题,我们还会回来。
如果我们退出循环体,则返回
true
,因为i
达到了s
的长度,而没有提前返回。现在,如果我错了,请原谅,但是根据文档,我们不应该在这里比较键吗?
什么文件?
另外,有人提到我是否理解同构,我不完全理解,我有一个大概的想法。
"同构"在这里的意思并不明显,但我们会弄清楚的。
现在我来分析一下这个函数。
理解循环功能的一种方法是从简单输入开始,然后"手动"遍历循环,根据需要遍历多次(从简单输入开始,这样就不必遍历太多次!)
让我们关注
mapS
变量,看看循环对它做了什么。因为mapS
是使用s
中的元素索引的,所以我们需要为s
选择一些字符串。让我们使用"abcab"
。程序仅在一条语句中更新
mapS
:现在让我们遍历循环,看看
mapS
是如何演化的,我们假设if
条件总是false。|
i
|s[i]
|循环体之前的mapS
|循环体后mapS
|| - ------|- ------|- ------|- ------|
| 无|
'a'
|(空)|* * 一米四二米一x**|| 1个|
'b'
|['a']=1
|一米四十五英寸一x一米四十六英寸一x|| 第二章|
'c'
|x一米四十八英寸x一米四十九英寸|x 1米50英寸x 1米51英寸xx 1米52英寸x|| 三个|
'a'
|x 1米54英寸1 x 1米55英寸1 x 1米56英寸1|* * 1米57英寸1 x1米58英寸1 x 1米59英寸1 x|| 四个|x1米60英寸1x|x1米61英寸1x x 1米62英寸1x 1米63英寸1x|一个米64个一个一个米65个一个一个米66个一个|
所以在循环体的开头,我们可以说:对于
s.substr(0, i)
中的每个字符c
(s
的第一个i
字符),mapS[c]
比s.substr(0, i)
中的c
的最后一个索引大一 *。注意,当
i == 0
为空字符串时,s.substr(0, i)
为空字符串。如前所述,
mapS
对任何未存储在map中的键返回0,因此我们将0视为"s.substr(0, i)
不包含c
"。根据0的这个含义,我们可以说,在循环体的开始,对于every
c
,mapS[c]
编码c
在s.substr(0, i)
中的最后一个索引如下:mapS[c] == 0
编码含义"c
不在s.substr(0, i)
中"。mapS[c] == x
编码含义"x - 1 < i
和s[x - 1] == c
以及s.substr(0, i)
在任何大于x - 1
的索引处不包含c
"。由于
mapT
的更新方式与mapS
完全相同,只是使用了t
中的字符,因此我们可以说它编码了与mapS
相同的含义,只是相对于t
而不是s
。现在我们可以分析
if
语句的条件了:mapS[s[i]] != mapT[t[i]]
.请记住,
s.substr(0, i)
不到达s[i]
;它恰好在s[i]
之前停止,即"abcab"[2]
是'c'
,并且"abcab".substr(0, 2)
是"ab"
;子字符串不以'c'
结尾。因此,在
if
条件下:mapS[s[i]]
是s.substr(0, i)
中的s[i]
的编码的最后一个索引。(记住"编码的最后一个索引"可以编码含义"没有这样的索引"。)mapT[t[i]]
是t[i]
在t.substr(0, i)
中的编码的最后索引。因此,如果这些编码的最后索引不同,则
if
语句使函数提前返回值false
。现在假设循环一直进行到
i == s.length()
,if
条件never为真,然后循环正常退出,并且程序已经证明,每当它在s
中看到某个字符c
,以及在t
中相同索引处看到某个对应的字符d
时,先前在s
和t
中的相同的较早(编码)索引处看到c
和d
。从这一点到更全面地理解
isIsomorphic
,这是一个小小的飞跃,但isIsomorphic(s, t)
的含义如下:是否有方法将
s
中出现的每个字符c
统一Map到t
中出现的唯一字符d
?反之亦然?如果有,isIsomorphic(s, t)
返回true。否则,返回false。请看这个例子:
isIsomorphic("abcab", "zyxzy")
。它返回true,因为s
中出现的字符与t
中出现的字符之间存在统一的双向Map:| S的|t|
| - ------|- ------|
| 项目a|z|
| b.人口基金|Y型|
| (c)秘书长的报告|x|
但是
isIsomorphic("abcab", "zyzzy")
是假的。s
中的'a'
和'c'
都必须Map到t
中的'z'
-但是t
中的'z'
只能Map回一个字符,而不能同时Map到'a'
和'c'
。这种统一、唯一、双向的Map称为bijection。
一个isomorphism总是一个双射,但通常有额外的要求,这取决于它定义的结构类型。例如,在图论中,你可以定义两个图的节点之间的双射,但同构也必须定义这两个图的边之间的双射。
此函数更好的名称可能是
bijectionExists
或samePattern
。chhqkbe12#
从理解代码开始首先需要理解它试图解决的问题。
两个字符串同构是指每个字符串A都可以Map到字符串B中的每个字符。
例如,
ACAB
和XCXY
同构。另外,
ACAB
和XCZY
是不同构的。那么,代码是如何解决这个问题的呢?我们将看看函数体的各个部分。
声明两个Map,每个Map对应一个字符串。它们都是空的。
这个循环只关心
s
的长度,我们已经遇到了一个障碍,如果我们想检查s -> t
和t !-> s
的单向Map,这个函数不能正确地完成,我会进一步说,如果s
和t
的长度不同,这个函数应该立即返回false
,因为我们保证如果t.length() < s.length()
的话会读取越界。继续:
我们必须将它们放在一起。
if
检查只是想知道对应的map元素是否具有相同的值。如果它们不具有相同的值,则在Map中存在不匹配,并且可以立即返回false。如果值确实匹配,则一起更新两个map。使用i + 1
是因为operator[]
处理map的方式。如果键不存在,尝试使用该键进行索引将在Map中创建一个条目,并将int
值初始化为0
。添加1
是避免误报的一种廉价方法。最后,如果您完成了循环而没有返回
false
,则假定字符串是同构的,并返回true。但是这个函数是假的,几乎可以说它检查的是"单向"同构,当
t
比s
长时,但是如果s
更长,它仍然可以返回true,并在这样做的同时调用未定义的行为。对我来说,更好的解决方案是存储 * actual character * Map,还需要跟踪第二个字符串中的唯一字符,并且第一次检查应该是等长。
输出:
我不想重复前面说过的话,但是对于一个类来说,这种代码结构是垃圾。它应该只是一个自由函数,或者 * 可能 * 插入到一个名称空间中。但是这超出了这个问题的范围。