- μ£Όμ΄μ§ λ¬Έμμ΄ λ°°μ΄
arr
μ λΆλΆ λ°°μ΄ arrβ
μ λν΄μ λͺ¨λ λ¬Έμμ΄μ μ΄μ΄λΆμμ λ μ€λ³΅λλ κΈμκ° μλ λΆλΆ λ°°μ΄μ μ΅λ κΈΈμ΄λ₯Ό ꡬνλ λ¬Έμ . - λΆλΆ λ°°μ΄μ μ 체 λ°°μ΄μμ μμμ κ°μμ μμλ₯Ό μ κ±°νμ λ λ§λ€μ΄μ§λ λ°°μ΄μ λ§νλ€.
- κ²°κ΅ λͺ¨λ λΆλΆ λ°°μ΄μ λν΄μ μ΄μ΄λΆμΈ λ¬Έμμ΄μ μ€λ³΅λ κΈμκ° μλμ§ νμΈνλ©΄ λλ λ¬Έμ μ΄λ€.
- λ¬Έμμ΄ λ°°μ΄μ μν κ° λ¬Έμλ³λ‘ μΆν μ¬λΆλ₯Ό λ§νΉνλ€.
- λ¬Έμμ΄μ μμ΄ μλ¬Έμλ‘λ§ κ΅¬μ±λμ΄μμΌλ―λ‘ μΆν μ¬λΆλ₯Ό Integerμ 0 ~ 25 λ²μ§Έ bitμ λ§νΉν μ μλ€.
- λ§μ½ νλμ λ¬Έμμ΄ λ΄μ μ΄λ―Έ μ€λ³΅μ΄ μλ€λ©΄ -1μ λλ €μ€λ€ (λͺ¨λ bitκ° λ§νΉλ¨).
- λ¬Έμμ΄ λ°°μ΄μ μμλλ‘ λ°λΌκ°λ©΄μ λ€μ μ¬νμ νμΈνλ€.
- νμ¬ μμΉ
index
λ₯Ό κΈ°μ€μΌλ‘, - (1) νμ¬ λ¬Έμμ΄μ λΆλΆ λ°°μ΄μ ν¬ν¨μν€μ§ μμ κ²½μ° μ΄μ΄λΆμΈ λ¬Έμμ΄μ κΈΈμ΄λ₯Ό ꡬνλ€.
- (2) νμ¬ λ¬Έμμ΄μ λΆλΆ λ°°μ΄μ ν¬ν¨μν¨ κ²½μ° μ΄μ΄λΆμΈ λ¬Έμμ΄μ κΈΈμ΄λ₯Ό ꡬνλ€. λ¨, νμ¬ λ¬Έμμ΄μ ν¬ν¨μμΌ°μ λ λ¬Έμ μ€λ³΅μ΄ λ°μνλμ§ νμΈνλ€.
- λ¬Έμμ μΆν μ¬λΆλ₯Ό bitλ‘ λ§νΉνμμΌλ―λ‘ νμ¬κΉμ§ λμ λ λ¬Έμμ΄μ μΆν μ¬λΆ λ§νΉ κ°
curr
κ³Ό νμ¬ λ¬Έμμ΄μ λ§νΉ κ° bits[index]
μ logical and &
μ°μ°νμ¬ κ°μ΄ 0μ΄ μλλΌλ©΄ μ€λ³΅μ΄ λ°μν κ²μΌλ‘ λ³Ό μ μλ€. - μ€λ³΅μ΄ λ°μνλ€λ©΄ ν΄λΉ λΆλΆ λ°°μ΄μ κ²½μ° κ²°κ³Ό κ°μμ μ μΈν΄μΌ νλ€.
- λ κ° μ€ κΈΈμ΄κ° κΈ΄ κ²μ λ΅μΌλ‘ νλ€.
class Solution {
int countBits(String s) {
int result = 0;
for (int i = 0; i < s.length(); ++i) {
int bit = 1 << (s.charAt(i) - 'a');
if ((result & bit) != 0)
return -1;
result |= bit;
}
return result;
}
int traverse(List<String> arr, int[] bits, int index, int curr) {
if (index >= bits.length)
return 0;
int count = traverse(arr, bits, index + 1, curr);
if (bits[index] != -1 && (curr & bits[index]) == 0) {
count = Math.max(count, traverse(arr, bits, index + 1, curr | bits[index]) + arr.get(index).length());
}
return count;
}
public int maxLength(List<String> arr) {
int[] bits = new int[arr.size()];
for (int i = 0; i < arr.size(); ++i) {
bits[i] = countBits(arr.get(i));
}
return traverse(arr, bits, 0, 0);
}
}