14. 最长公共前缀
class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length == 0) return ""; //初始化,res为第一个字符串 String res = strs[0]; //依次与每个字符串比较,碰到不一样的用substring截取相同的部分 for(int i = 1; i < strs.length; i++){ int j = 0; for(; j < res.length() && j < strs[i].length(); j++){ if(res.charAt(j) != strs[i].charAt(j)) break; } res = res.substring(0,j); } return res; } }
剑指 Offer 48. 最长不含重复字符的子字符串
class Solution { public int lengthOfLongestSubstring(String s) { HashMap<Character, Integer> map = new HashMap<>(); int tmp = 0, res = 0; for(int j = 0; j < s.length(); j++){ int i = map.getOrDefault(s.charAt(j), -1); map.put(s.charAt(j), j); //tmp用来存放以字符s[j]为结尾的 “最长不重复子字符串” 的长度 //哈希表中没有重复的情况下,j++,而i始终为-1 //则问号前的式子永远为真,j往后移,最长不重复字串长度也+1 //哈希表中有重复的情况下,更新为j-i,i是哈希表中找到的重复元素的下标 tmp = tmp < j - i ? tmp + 1 : j - i; res = Math.max(tmp, res); } return res; } }
1143. 最长公共子序列
class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); char[] sc1 = text1.toCharArray(); char[] sc2 = text2.toCharArray(); //dp[i][j] 代表sc1 的前i-1个字符、sc2的前j−1的字符,形成的最长公共子序列长度 //dp[m][n] 就是答案 int dp[][] = new int[m+1][n+1]; for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ //两个字符串最后一位相等,最长公共子序列+1 if(sc1[i-1] == sc2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; //不相等,取两项中较大的一项 else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } return dp[m][n]; } }