【Leetcode 每日一题】3083. 字符串及其反转中是否存在同一子字符串

问题背景

给你一个字符串 $s$，请你判断字符串 $s$ 是否存在一个长度为 $2$ 的子字符串，在其反转后的字符串中也出现。
如果存在这样的子字符串，返回 $true$；如果不存在，返回 $false$。

数据约束

• $1\le s.length\le 100$
• 字符串 $s$ 仅由小写英文字母组成。

解题过程

需要判断的字串长度固定是 $2$，那就可以偷懒用嵌套循环搭配二维数组来解决。如果没有这样的条件，就要考虑回溯之类的做法了。
这里刚好能够联系一下位运算的使用，参考 灵神的总结。

具体实现

二维数组

class Solution {public boolean isSubstringPresent(String s) {char[] chS = s.toCharArray();int n = chS.length;boolean[][] vis = new boolean[26][26];for(int i = 1; i < n; i++) {int x = chS[i - 1] - 'a';int y = chS[i] - 'a';vis[x][y] = true;if(vis[y][x]) {return true;}}return false;}
}

位运算

class Solution {public boolean isSubstringPresent(String s) {char[] chS = s.toCharArray();int n = chS.length;int[] vis = new int[26];for(int i = 1; i < n; i++) {int x = chS[i - 1] - 'a';int y = chS[i] - 'a';vis[x] |= 1 << y;if((vis[y] >> x & 1) != 0) {return true;}}return false;}
}