leetcode - shortest-distance-to-a-character 자바 풀이
문제
해설
- 백트레킹(재귀)으로 풀었는데
- 재귀 굳이 쓰기보단 for문도 쓸만할꺼같긴 하다
백트레킹
private void goLeft(int idx, char[] map, int[] ans, int len) {
//<< --
if (idx == -1) {
return;
} else {
ans[idx] = Math.min(ans[idx], len);
goLeft(idx - 1, map, ans, len + 1);
}
}
- Left 기준으로 설명하면(인덱스가 작아지는 방향)
- Right 는 그냥 레프트의 반대방향으로 가면 되는거라 생략!
코드
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public int[] shortestToChar(String s, char c) {
char[] map = s.toCharArray();
int[] ans = new int[s.length()];
Arrays.fill(ans, s.length());
//get starting point
List<Integer> stp = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
if (map[i] == c) {
stp.add(i);
}
}
for (int i = 0; i < stp.size(); i++) {
goLeft(stp.get(i), map, ans, 0);
goRight(stp.get(i), map, ans, 0);
}
return ans;
}
private void goRight(int idx, char[] map, int[] ans, int len) {
// >> ++
if (idx >= ans.length) {
return;
} else {
ans[idx] = Math.min(ans[idx], len);
goRight(idx + 1, map, ans, len + 1);
}
}
private void goLeft(int idx, char[] map, int[] ans, int len) {
//<< --
if (idx == -1) {
return;
} else {
ans[idx] = Math.min(ans[idx], len);
goLeft(idx - 1, map, ans, len + 1);
}
}
public static void main(String[] args) {
tester("loveleetcode", 'e', new int[]{3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0});
tester("aaab", 'b', new int[]{3, 2, 1, 0});
}
public static void tester(String s, char c, int[] ans) {
Solution sol = new Solution();
int[] ret = sol.shortestToChar(s, c);
for (int i = 0; i < ans.length; i++) {
if (ans[i] != ret[i]) {
System.out.println("NG");
System.out.println("your return : " + Arrays.toString(ret));
System.out.println("Answer : " +Arrays.toString(ans));
return;
}
}
System.out.println("OK");
}
}
Author And Source
이 문제에 관하여(leetcode - shortest-distance-to-a-character 자바 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@d-h-k/leetcode-shortest-distance-to-a-character-자바-풀이
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
private void goLeft(int idx, char[] map, int[] ans, int len) {
//<< --
if (idx == -1) {
return;
} else {
ans[idx] = Math.min(ans[idx], len);
goLeft(idx - 1, map, ans, len + 1);
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public int[] shortestToChar(String s, char c) {
char[] map = s.toCharArray();
int[] ans = new int[s.length()];
Arrays.fill(ans, s.length());
//get starting point
List<Integer> stp = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
if (map[i] == c) {
stp.add(i);
}
}
for (int i = 0; i < stp.size(); i++) {
goLeft(stp.get(i), map, ans, 0);
goRight(stp.get(i), map, ans, 0);
}
return ans;
}
private void goRight(int idx, char[] map, int[] ans, int len) {
// >> ++
if (idx >= ans.length) {
return;
} else {
ans[idx] = Math.min(ans[idx], len);
goRight(idx + 1, map, ans, len + 1);
}
}
private void goLeft(int idx, char[] map, int[] ans, int len) {
//<< --
if (idx == -1) {
return;
} else {
ans[idx] = Math.min(ans[idx], len);
goLeft(idx - 1, map, ans, len + 1);
}
}
public static void main(String[] args) {
tester("loveleetcode", 'e', new int[]{3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0});
tester("aaab", 'b', new int[]{3, 2, 1, 0});
}
public static void tester(String s, char c, int[] ans) {
Solution sol = new Solution();
int[] ret = sol.shortestToChar(s, c);
for (int i = 0; i < ans.length; i++) {
if (ans[i] != ret[i]) {
System.out.println("NG");
System.out.println("your return : " + Arrays.toString(ret));
System.out.println("Answer : " +Arrays.toString(ans));
return;
}
}
System.out.println("OK");
}
}
Author And Source
이 문제에 관하여(leetcode - shortest-distance-to-a-character 자바 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@d-h-k/leetcode-shortest-distance-to-a-character-자바-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)