pkg.gl

sigam-Zq: 针对题目

给你一个字符串 s ，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在其反转后的字符串中也出现。

如果存在这样的子字符串，返回 true；如果不存在，返回 false 。

存在一个位运算解法

func isSubstringPresentLeetCode2(s string) bool { h := make([]int, 26) for i := 0; i+1 < len(s); i++ { x, y := s[i]-'a', s[i+1]-'a' h[x] |= (1 << y) if (h[y]>>x)&1 != 0 { return true } } return false }

存在以下问题

h[x] |= (1 << y) 这里的位或运算和 1左移 y位写入 h[x]在下面要起到什么作用，这一步有什么作用

2 (h[y]>>x) 上面的 h[y]>>x 把 h[y] 随后右移 x 位实现了什么效果，起到了什么作用

这里右移之后通过&1 != 0判断该数的个位数是否是奇数这里起到了什么作用

for 循环中重复对 h[x] |= (1 << y) 进行位移或运算，这里会达到什么效果
通过上面的位运算怎么实现反转后的字符串中也出现的判断的

GitHub Copilot: 1.

h[x] |= (1 << y)

：这一步的作用是将字符

s[i+1]

的信息记录在字符

s[i]

对应的位置上。具体来说，1 << y 会生成一个只有第

位为 1 的整数，然后通过 |= 操作将这个整数与

h[x]

进行位或运算，从而在

h[x]

中记录下字符

s[i+1]

的信息。

(h[y] >> x)：这一步的作用是检查字符

s[i+1]

是否已经记录了字符

s[i]

的信息。具体来说，

h[y] >> x

会将

h[y]

右移

位，从而将第

位移到最低位。然后通过 & 1 操作检查最低位是否为 1，从而判断字符

s[i+1]

是否已经记录了字符

s[i]

的信息。

for 循环中重复对

h[x] |= (1 << y)

进行位移或运算：这一步的作用是不断更新

数组，记录每个字符后面出现的字符信息。通过这种方式，可以在遍历字符串的过程中逐步构建字符之间的关系。

通过上面的位运算实现反转后的字符串中也出现的判断：通过

h[x] |= (1 << y)

操作，记录了每个字符后面出现的字符信息。然后通过 (h[y] >> x) & 1 != 0 操作，检查字符

s[i+1]

是否已经记录了字符

s[i]

的信息。如果存在这样的记录，说明存在一个长度为 2 的子字符串，在其反转后的字符串中也出现。

sigam-Zq: 能否举个具体例子？

GitHub Copilot: 当然可以。让我们通过一个具体的例子来解释这个算法的工作原理。

假设字符串

为 "abca"。

初始化一个长度为 26 的数组

，每个元素初始值为 0。

h := make([]int, 26)

遍历字符串

，对于每一对相邻字符

s[i]

和

s[i+1]

，进行以下操作：

第一次迭代 (

i = 0

): -

x = s[0] - 'a' = 'a' - 'a' = 0

y = s[1] - 'a' = 'b' - 'a' = 1

h[0] |= (1 << 1)

，即

h[0] = 0 | (1 << 1) = 0 | 2 = 2

数组更新为 [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] - (h[1] >> 0) & 1 = (0 >> 0) & 1 = 0 & 1 = 0，不满足条件，继续下一次迭代。

第二次迭代 (

i = 1

): -

x = s[1] - 'a' = 'b' - 'a' = 1

y = s[2] - 'a' = 'c' - 'a' = 2

h[1] |= (1 << 2)

，即

h[1] = 0 | (1 << 2) = 0 | 4 = 4

数组更新为 [2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] - (h[2] >> 1) & 1 = (0 >> 1) & 1 = 0 & 1 = 0，不满足条件，继续下一次迭代。

第三次迭代 (

i = 2

): -

x = s[2] - 'a' = 'c' - 'a' = 2

y = s[3] - 'a' = 'a' - 'a' = 0

h[2] |= (1 << 0)

，即

h[2] = 0 | (1 << 0) = 0 | 1 = 1

数组更新为 [2, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] - (h[0] >> 2) & 1 = (2 >> 2) & 1 = 0 & 1 = 0，不满足条件，继续下一次迭代。

遍历结束，没有找到满足条件的子字符串，返回 false。

通过这个例子，我们可以看到，算法通过位运算记录了每个字符后面出现的字符信息，并检查是否存在反转后的子字符串。

# README