문제

해설

• 백트레킹(재귀)으로 풀었는데
• 재귀 굳이 쓰기보단 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");
    }


}