In this question, I spent three hours and did not finally solve it. I would like to share the process and thoughts of solving the problem and learn the backtracking algorithm
1. The subject
M1239
2. Personal problem-solving process
TDD- test-driven development, using Junit5 to cover different scenarios with unit tests to modify the code step by step.
2.1 Unit Test
class M1239Test {
static Stream<Arguments> testCaseParams(a) {
return Stream.of(
Arguments.of(Collections.singletonList("abcd"), 4),
Arguments.of(Arrays.asList("b"."c"), 2),
Arguments.of(Arrays.asList("a"."b"."c"), 3),
Arguments.of(Arrays.asList("b"."c"."abc"), 3),
Arguments.of(Arrays.asList("a"."b"."ab"), 2),
Arguments.of(Arrays.asList("b"."c"."aabc"), 2),
Arguments.of(Arrays.asList("a"."abc"."d"."de"."def"), 6), // xxxxx
Arguments.of(Arrays.asList("a"."b"."c"."cd"."de"."def"), 6) // xxx
);
}
@MethodSource("testCaseParams")
@ParameterizedTest
void maxLengthTest(List<String> arr, int expectedLength) {
M1239 m1239 = new M1239();
intlength = m1239.maxLength(arr); Assertions.assertEquals(expectedLength, length); }}Copy the code2.2 Implement the problem logic
package com.learning.midium;
import java.util.List;
* Given a string array arr, string S is the concatenated string of some subsequence of arR. If every character in S occurs only once, then it is a viable solution. * <p> * Please return the longest length of all possible solutions s. * *@author wcy
*/
public class M1239 {
public int maxLength(List<String> arr) {
int arrSize = arr.size();
if (arrSize == 1) {
return arr.get(0).length();
}
// The maximum valid length, 0 by default
int validLength = 0;
/** * valid concatenation: * 1. No repeated characters ** invalid concatenation: * 1. Add length over 26 * 2. Repeated characters: traversal contrast */
for (int i = 0; i < arrSize; i++) {
if (repetitionSelfInspection(arr.get(i))) {
continue;
}
StringBuilder appendStr = new StringBuilder(arr.get(i));
for (int j = i + 1; j < arrSize; j++) {
String jStr = arr.get(j);
if (repetitionSelfInspection(jStr)) {
continue;
}
For (int j...); for(int j...) cycle
boolean charRepetition = false;
char[] iStrChars = appendStr.toString().toCharArray();
char[] jStrChars = jStr.toCharArray();
for (char iStrChar : iStrChars) {
for (char jStrChar : jStrChars) {
// repeat the character, allBreak = true
if (charRepetition = (iStrChar == jStrChar)) {
break; }}if (charRepetition) {
break; }}if (charRepetition) {
continue;
}
// If no character is repeated, append to check whether the character length exceeds 26
if ((appendStr.length() + jStr.length()) > 26) {
continue;
}
appendStr.append(jStr);
}
// Confirm the length, save the longest result
int appendStrLength = appendStr.length();
validLength = Math.max(appendStrLength, validLength);
}
return validLength;
}
/** * Checks for duplicate characters **@returnTrue - contains, false - does not contain */
private boolean repetitionSelfInspection(String str) {
char[] chars = str.toCharArray();
for (char aChar : chars) {
if(str.indexOf(aChar) ! = str.lastIndexOf(aChar)) {return true; }}return false; }}Copy the code2.3 Personal solution problem
Through the description of the topic, the problem is solved intuitively, starting from the simplest scenario, and finally after the emergence of [” A “, “ABC “,” D “, “de”, “def”], the existing code can not solve the problem, this idea is illogical.
The main problem with modern codes is that there is no way to handle this in a two-layer loop. After ABC + d, the following loop will correctly replace d with def when it encounters def, but def will be skipped because it is a repeated string.
3. Official solution (backtracking + bit operation)
3.1 Official Java solution
Author: Leetcode-Solution Link: leetcode-cn.com/problems/ma… Source: LeetCode
class Solution {
int ans = 0;
public int maxLength(List<String> arr) {
List<Integer> masks = new ArrayList<Integer>();
for (String s : arr) {
int mask = 0;
for (int i = 0; i < s.length(); ++i) {
int ch = s.charAt(i) - 'a';
if (((mask >> ch) & 1) != 0) { // If the mask has ch, then s contains repeated letters and cannot form a feasible solution
mask = 0;
break;
}
mask |= 1 << ch; // add ch to mask
}
if (mask > 0) {
masks.add(mask);
}
}
backtrack(masks, 0.0);
return ans;
}
public void backtrack(List<Integer> masks, int pos, int mask) {
if (pos == masks.size()) {
ans = Math.max(ans, Integer.bitCount(mask));
return;
}
if ((mask & masks.get(pos)) == 0) { // Masks and masks[pos] have no common elements
backtrack(masks, pos + 1, mask | masks.get(pos));
}
backtrack(masks, pos + 1, mask); }}Copy the code3.2 In the first step, build filtered strings with no repeated letters
Traverses the array of strings to filter out strings that have no duplicate letters and puts their binary number into the array masks
Since the string forming the feasible solution contains only lowercase letters and no repeated elements, 26 English lowercase letters, regardless of the order, can be shown as follows:
- ‘zdcba’ –> ’10 0000 0000 0000 0000 0000 1111′
- ‘0 0000 0000 0000 0000 0000 0000 0001’
- ‘ABC’ –> ’00 0000 0000 0000 0000 0000 0111′
- ‘cab’ –> ’00 0000 0000 0000 0000 0000 0111′
Code implementation:
// if s.charat (I) == 'a', then ch = 0, representing the first binary bit
// if s.charat (I) == 'c', then ch = 2, representing the third digit in binary
// And so on... In this way, the unduplicated letter string is converted to a binary number, saved as Integer into the masks array
int ch = s.charAt(i) - 'a';
// For example: "ABC"
// fori i=0; ch = 'c'-'a' = 2, mask=0; (mask >> ch) = 0000 & 0001 = 0000; 0! =0 break; mask |= 1 << ch = 0100
// i=1; ch = 'b'-'a' = 1, mask=0100; (mask >> ch) = 0010 & 0001 = 0000; 0! =0 break; mask |= (1 << ch) -> 0100 |= 0010 = 0110
// i=2; ch = 'a'-'a' = 0, mask=0110; (mask >> ch) = 0110 & 0001 = 0000; 0! =0 break; mask |= (1 << ch) -> 0110 |= 0001 = 0111
// get the binary value 0111 for "ABC"
if (((mask >> ch) & 1) != 0) { // If the mask has ch, then s contains repeated letters and cannot form a feasible solution
mask = 0;
break;
}
Copy the code3.3 Step 2: Backtracking
In the first step, convert an array of strings to a binary array without repeating letters. Take [“a”, “b”, “c”, “CD “, “de”, “def”] as an example. The converted array (binary representation here) is:
- a: 0001
- b: 0010
- c: 0100
- cd: 1100
- de: 0001 1000
- def: 0011 1000
public void backtrack(List<Integer> masks, int pos, int mask) {
if (pos == masks.size()) {
ans = Math.max(ans, Integer.bitCount(mask));
return;
}
if ((mask & masks.get(pos)) == 0) { // Masks and masks[pos] have no common elements
backtrack(masks, pos + 1, mask | masks.get(pos));
}
backtrack(masks, pos + 1, mask); // There are common elements
}
// ans=0, masks=[0001, 0010, 0100, 1100, 0001 1000, 0011 1000] => (["a", "b", "c", "cd", "de", "def"])
// 1. Pos =0,mask=0, mask & mask. get(pos) --> 0000&0001 = 0000 == 0
/ / backtrack (masks, pos + 1, mask | masks. Get (pos)); 0000 | 0001 = 0001; => Backtrack (masks, 1, 0001), next level recursion
// 2. Pos =1 does not equal mask. Size =6,mask=0001; Get (pos) > 0001&0010 = 0000 == 0, no public elements in the masks (masks, 2, 0011)
Pos =2 mask=0011, 0011&0100 = 0000, no public element backtrack(masks, 3, 0111)
// 4. pos=3 mask=0111, 0111 & 1100 = 0100 ! Backtrack (masks, 4, 0111) => Backtrack (masks, 4, 0111)
Pos =4 mask=0111, 0111&0001 1000 =0, no public element backtrack(masks, 5, 0001 1111)
// 6. pos=5 mask=0001 1111, 0001 1111 & 0011 1000 = 0001 1000; Public backtrack(masks, 6, 0001 1111)
// 7. pos=6 mask=0001 1111, pos == masks.size(); Ans = Max (0, integer.bitcount (mask)) =0001 1111 Return recursion <<<<< ant=0001 1111
Pos =5 mask=0001 1111 There are common elements returned recursively
Backtrack (masks, pos + 1, mask)
Pos =5 mask=0111 (masks, 5, 0011 1111)
// ->7. pos=6 mask=0011 1111, pos == masks.size(); Ans = Max (0, integer.bitcount (mask)) =0011 1111 return recursion <<<<< ant=0011 1111
Ant = 0011 1111 = abcdef
Copy the code4. Backtracking algorithm
What is a backtracking algorithm, in layman’s terms, similar to the movie “The Butterfly Effect”, at critical turning points of events, making different choices in order to achieve the desired outcome.
[” A “, “b”, “c”, “CD “, “de”, “def”]. When ABC and DE are connected in series, def will be judged as a repeated field. So you have to go back to de and not series it, with def, to get the expected value.