当前位置：网站首页>String exercise summary 2
String exercise summary 2
2022-06-24 22:17:00 【Dream building boy】
Catalog
3、 ... and . Find all palindrome substrings of a string （ The central expansion method ）
5、 ... and . Split palindrome string （ The split string is all palindromes ）
6、 ... and . Restore IP Address
7、 ... and . Minimum cover substring
8、 ... and . Letter combination of telephone number
One . Longest text substring
1. subject
Give you a string s, find s The longest palindrome substring in .
Example ：
Input ：s = "babad" Output ："bab" explain ："aba" It's the same answer .
2. The illustration
3. Code
public String longestPalindrome(String s) {
// Set two pointers to save the start and end positions of the palindrome string
int begin = 0;
int end = 0;
for(int i=0; i<s.length(); i++) {
// The string length has parity , So we need to find the maximum value in parity
int len1 = huiWenLen(s, i, i);
int len2 = huiWenLen(s, i, i+1);
int len = Math.max(len1, len2);
if(len>end-begin) {
// When it's even , Such as abb（ The result is bb） At this time, if will be counted more begin=i-len/2 You'll lose one , Cause error
begin = i-(len-1)/2;
end = i+len/2;
}
}
// The string is intercepted from begin Start , To end+1 end （ It doesn't contain end+1）
return s.substring(begin, end+1);
}
// Start from the current element to both sides to find whether it is a palindrome string
public int huiWenLen(String str, int left, int right) {
int l = left, r = right;
while(l>=0 && r<str.length() && str.charAt(l)==str.charAt(r)) {
l--;
r++;
}
return r-l-1;
}Two . Find the full arrangement of all sets of the array （ It is the same as finding all substrings of a string ）
1. subject
Now there is a set of integers without repeating elements S, seek S All subsets of
Be careful ：
The elements in the subset you give must be arranged in ascending order
The given solution set cannot have duplicate elements
Example ：
Input ：[1,2,3]
Return value ：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
2. The illustration
3. Code
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(S==null || S.length==0) {
return res;
}
for(int i=0; i<=S.length; i++) {
// Control length , Call a recursive function to find
dfsColl(S, 0, i, res, new ArrayList<>());
}
return res;
}
public void dfsColl(int[] arr, int begin,int len , ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
// Meet the specified length , Just add it to the result set
if(len == list.size()) {
res.add(new ArrayList<>(list));
}
// Look back from the starting position
for(int i=begin; i<arr.length; i++) {
// Add the current element to list in
list.add(arr[i]);
// And then recursively look back
dfsColl(arr, i+1, len, res, list);
// After finding the specified length of the current element , Delete current element
list.remove(list.size()-1);
}
}3、 ... and . Find all palindrome substrings of a string （ The central expansion method ）
1. subject
Give you a string s , Please count and return this string Palindrome string Number of .
Palindrome string Is reading the same string as reading it backwards .
Substring Is a sequence of consecutive characters in a string .
A substring with different start or end positions , Even if it's made up of the same characters , It's also seen as a different substring
source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/palindromic-substrings
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Example ：s="aaba"
Output res= 6 , The palindrome string has a ,a ,b ,a ,aa ,aba
2. The idea diagram
（1） Method 1
First of all, a character must be palindrome , When centered on this character , Continue to separate with left and right When extending to both sides and validating as a substring , This is a kind of thinking , But there is a situation , That is, the same two characters can also be formed as a center to spread out , for example aa, At this time, we have to distinguish according to parity （ There may be a question , There may also be 3 Or 4 As a palindrome Center ; because 3 One is 1 Extensions of ,4 One is 2 Extensions of , So we just discuss it according to parity 2 And 1 individual ）; Use 2 When expanding with characters as the center , Need to judge this 2 Characters are equal to each other before expansion .
（2） Method 2
Ideas and methods 1 identical , It is only merged when expanding according to odd and even numbers , Reduce the amount of code .
First of all, we can see from the above processing results , All in all s.length*2-1 Centers need to be expanded ; Then find the relationship , Then we can sum up , from 【0,s.length*2-1】 Between , All the left edges left=i/2; All right edges right=left+i%2;
After that, it is solved by the method of center expansion （ Even numbers are also determined in the process of expansion 2 Whether the characters as the center are equal ）.
3. Code
（1） Method 1
public int countSubstrings(String s) {
// Here itself is palindrome , So first count yourself
int res = s.length();
// Extend with odd numbers
for(int i=0; i<s.length(); i++) {
int left = i-1;
int right = i+1;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
res++;
left--;
right++;
}
}
// Extend with even numbers
for(int i=0; i<s.length()-1; i++) {
// explain 2 Characters can be used as the Extension Center
if(s.charAt(i)==s.charAt(i+1)) {
res++;
int left = i-1;
int right = i+2;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
res++;
left--;
right++;
}
}
}
return res;
}（2） Method 2
public int countSubstrings(String s) {
int res = 0;
// All in all, you need to match len*2-1 Time , Then it will expand to both sides according to parity , If it's palindrome
//res++, Otherwise, judge the next one （ Pay attention to the boundary problem in the process of judgment ）
for(int i=0; i<s.length()*2-1; i++) {
int left = i/2;
int right = left+i%2;
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
res++;
left--;
right++;
}
}
return res;
}Four . Find binary sum
1. subject
Given two binary numbers represented by strings , Back to their and .
Data range ： The string length satisfies 1\le n \le 10^5 \1≤n≤105 , The string contains only 0 and 1, And ensure that except 0 There is no leading zero for binary numbers other than .
Example ：
Input ："101","1"
Return value ："110"
2. The idea diagram
Ideas ：
Ideas ：
First, you need to save the number to be carried and name it carry（ The initial value is 0）,
Then calculate the sum of the current position ( Value containing carry ), sum=A.charAt(i)+B.charAt(i),
When calculating the sum of the current position, you also need to judge whether the length of the source string is exceeded each time , If more than , The current result position is 0
The next step is to save the carry values , Use for the next sum
Then save the sum of the current position
The illustration ：
3. Code
public String binaryAdd (String A, String B) {
// write code here
int aL = A.length()-1;
int bL = B.length()-1;
// It means carry
int carry = 0;
StringBuilder sb = new StringBuilder();
while(aL>=0 || bL>=0 || carry>0) {
// Get the current result of each string
int a = (aL<0?'0':A.charAt(aL--))-'0';
int b = (bL<0?'0':B.charAt(bL--))-'0';
// Sum up （ Contains the carry of the low bit and the sum of the high bit ）
int sum = a+b+carry;
// Save carry results
carry = sum/2;
// Save the result of the current position after carry
sb.append(sum%2);
}
// Finally, reverse the spliced results
return sb.reverse().toString();
}5、 ... and . Split palindrome string （ The split string is all palindromes ）
1. subject
Give you a string s, Would you please s Split into some substrings , So that each substring is Palindrome string . return s All possible segmentation schemes .
Example ：
Input ：s = "aab" Output ：[["a","a","b"],["aa","b"]]
2. The idea diagram
3. Code
List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
char[] charArray = s.toCharArray();
dfs(charArray, 0, s.length(), new ArrayList<>());
return res;
}
// Find all palindrome substrings
public void dfs(char[] charArray, int index, int len, ArrayList<String> list) {
// Description string has been processed
if(index == len) {
res.add(new ArrayList<>(list));
return;
}
// Take one part in turn , First judge whether it is palindrome , If it is a palindrome, it will be processed downward , If it's not palindrome , Skip the current loop
for(int i=index; i<len; i++){
if(!isPartion(charArray, index, i)) {
continue;
}
list.add(new String(charArray, index, i-index+1));
dfs(charArray, i+1, len, list);
// After processing the substring of the current layer , Delete the , Then process the following substrings of the current layer
list.remove(list.size()-1);
}
}
// Judge whether it is a palindrome string
public boolean isPartion(char[] charArray, int left, int right) {
while(left < right) {
if(charArray[left++] != charArray[right--]) {
return false;
}
}
return true;
}
6、 ... and . Restore IP Address
1. subject
It works IP Address It's just four integers （ Each integer is located in 0 To 255 Between the composition of , And it can't contain leading 0）, Use... Between integers '.' Separate .
for example ："0.1.2.201" and "192.168.1.1" yes It works IP Address , however "0.011.255.245"、"192.168.1.312" and "[email protected]" yes Invalid IP Address .
Given a string containing only numbers s , It is used to indicate a IP Address , Returns all possible valid IP Address , These addresses can be accessed through s Insert '.' To form . you You can't Reorder or delete s Any number in . You can press whatever Return the answers in order .
source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/restore-ip-addresses
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
2. The idea diagram
3. Code
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
int len = s.length();
dfs(s, 0, 0, len, new ArrayList<String>());
return res;
}
// Perform a deep search for processing
public void dfs(String s, int beign, int count, int len, ArrayList<String> list) {
// Processing to the end , Just save and return
if(beign == len) {
if(count==4)
res.add(String.join(".", list));
return;
}
// prune （ The length of the characters is less than the number of intercepts , Characters longer than the number of interceptions 3 times ）
if(len-beign<(4-count) || len-beign>3*(4-count)) {
return;
}
// Handle the current 3 Characters （1,2,3 Connect them separately ）
for(int i=0; i<3; i++) {
if(i+beign>=len) {
break;
}
int tmp = segment(s, beign,beign+i+1);
if(tmp != -1){
list.add(""+tmp);
dfs(s, beign+i+1, count+1, len, list);
// to flash back
list.remove(list.size()-1);
}
}
}
// Determine whether the intercepted string conforms to ip Specification of address , Conformity is translated into numbers
public int segment(String s, int left, int right) {
// When the first length is greater than 1 And the first is 0 When you return to
if(right-left>1 && s.charAt(left)=='0') {
return -1;
}
// Find the string of 10 Base result
int res = 0;
for(int i=left; i<right; i++) {
res = res*10+s.charAt(i)-'0';
}
// Description over ip length
if(res>255) {
return -1;
}
return res;
}7、 ... and . Minimum cover substring
1. subject
Give you a string s 、 A string t . return s Covered by t The smallest string of all characters . If s There is no coverage in t Substring of all characters , Returns an empty string "" .
Example ：
2. The idea diagram
The solution idea is to use two hash Table to store strings s and t The number of times characters appear in , First count the string t, After that, we can use the idea of sliding window to take s Characters in are added to hash in , It is equivalent to expanding the window , In the statistical process, if The element on the left side of the window is not in t Contain or contain but repeat more , In this case, you need to reduce the size of the window , These operations are based on hash Table to operate . One more in the middle count Mark whether the element in the window already contains t All characters in , I need one more len To identify whether it is the smallest covering substring .
3. Code
public String minWindow(String s, String t) {
HashMap<Character,Integer> ms = new HashMap<>();
HashMap<Character,Integer> mt = new HashMap<>();
// Statistics first t The number of times characters appear in
for(int i=0; i<t.length(); i++) {
mt.put(t.charAt(i), mt.getOrDefault(t.charAt(i), 0)+1);
}
// Save the result value
String res="";
// Record the current length , Then shorten the string according to the length
int len = Integer.MAX_VALUE;
//left and right Represents the left and right boundaries of the sliding window ;count Record t stay s Number of existing in
for(int left=0,right=0,count=0; right<s.length(); right++) {
// Put the element first ms in
ms.put(s.charAt(right), ms.getOrDefault(s.charAt(right), 0)+1);
// Determine whether the character also appears in t in
if(mt.containsKey(s.charAt(right))) {
// You also need to determine whether the current character is t necessary （ Avoid repeated useless characters ）
if(ms.get(s.charAt(right))<=mt.get(s.charAt(right))) {
count++;
}
}
// If s Of left The element of position is not contained in t in or The number of characters exceeds the specified number , Then delete the character
while(left<right && (!mt.containsKey(s.charAt(left)) ||
ms.get(s.charAt(left))>mt.get(s.charAt(left)))) {
ms.put(s.charAt(left), ms.get(s.charAt(left))-1);
left++;
}
// Satisfy count length then （ according to len） Determine whether to shorten the interval , If shortened , modify res
if(count==t.length() && right-left+1<len) {
len = right-left+1;
res = s.substring(left, right+1);
}
}
return res;
}8、 ... and . Letter combination of telephone number
1. subject
Given a number only 2-9 String , Returns all the letter combinations it can represent . You can press In any order return .
Example ：
Input ：digits = "23" Output ：["ad","ae","af","bd","be","bf","cd","ce","cf"]
2. Graphic thinking
The character corresponding to each number is processed by recursive backtracking , When recursion reaches the end of the string , Just save the results , End recursion .
3. Code
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if(digits.length()==0) {
return res;
}
Map<Character, String> map = new HashMap<>();
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
dfs(0, digits, new StringBuilder(), map, res);
return res;
}
public void dfs(int index, String digits, StringBuilder sb, Map<Character, String> map, List<String> res) {
if(index==digits.length()) {
// Indicates that the number has been processed to the end
res.add(new String(sb));
return;
}
// Not finished with , Just process the number of the current position ( Get all the characters corresponding to the current number )
String str = map.get(digits.charAt(index));
// Loop through the current character and recursively process the next number
for(int i=0; i<str.length(); i++) {
sb.append(str.charAt(i));
// recursive
dfs(index+1, digits, sb, map, res);
// to flash back
sb.deleteCharAt(sb.length()-1);
}
}边栏推荐
- The process from troubleshooting to problem solving: the browser suddenly failed to access the web page, error code: 0x80004005, and the final positioning: "when the computer turns on the hotspot, the
- 04A中断的配置
- In the first year of L2, arbitrum nitro was upgraded to bring more compatible and efficient development experience
- 排查到解决问题的过程：浏览器突然无法访问网页，错误代码：0x80004005，最终定位：“电脑打开热点，电脑就不能上网了”
- Find the maximum value in each tree row [extension of one of the hierarchical traversals]
- PostMan工具介绍及安装使用
- 专科出身，2年进苏宁，5年跳阿里，论我是怎么快速晋升的？
- Two implementation methods of stack
- 如何抓手机的包进行分析，Fiddler神器或许能帮到您！
- Development trend and path of SaaS industry in China
猜你喜欢
The logic of "Ali health" has long changed
【OpenCV 例程200篇】209. HSV 颜色空间的彩色图像分割
Collapse code using region
first-order-model实现照片动起来（附工具代码） | 机器学习
![[notes of wuenda] fundamentals of machine learning](/img/71/6192a75446fa7f79469a5483ececc6.jpg)
[notes of wuenda] fundamentals of machine learning
Maximum flow problem
C language - keyword 1
985测试工程师被吊打，学历和经验到底谁更重要？
Huada 04A operating mode / low power consumption mode
Interviewer: you said you are proficient in redis. Have you seen the persistent configuration?
随机推荐
Flutter 库冲突问题解决
Opengauss kernel: simple query execution
字符串习题总结2
KT6368A蓝牙双模透传芯片软件版本选型说明
如何比较两个或多个分布：从可视化到统计检验的方法总结
Detailed explanation of agency mode
60 divine vs Code plug-ins!!
EasyBypass
KT6368A蓝牙芯片的主从机之前透传功能说明，2.4G跳频自动连接
Reduce the pip to the specified version (upgrade the PIP through CMP and reduce it to the original version)
The process from troubleshooting to problem solving: the browser suddenly failed to access the web page, error code: 0x80004005, and the final positioning: "when the computer turns on the hotspot, the
SAP interface debug setting external breakpoints
嵌入式开发：技巧和窍门——干净地从引导加载程序跳转到应用程序代码
Ideal L9, new trend of intelligent cockpit
Binary search tree template
短视频商城系统，scroll-view如何自适应页面剩余高度
印刷行业的ERP软件的领头羊
leetcode_ one thousand three hundred and sixty-five
Disk structure
The logic of "Ali health" has long changed