https://leetcode-cn.com/problems/freedom-trail/

别的不说，就比如在前往 key[i] 时，逆时针和顺时针波动以到达的一个最近位置的花费是一样的，dp 如何表达这件事？

dfs 用过了，超时。。。

import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set;  public class Solution {      private String rring;     private String kkey;     private Map<Character, Set<Integer>> ringMap;     private int ans = Integer.MAX_VALUE;      public int findRotateSteps(String ring, String key) {         rring = ring;         kkey = key;         ringMap = new HashMap<>();         for (int i = 0; i < ring.length(); i++) {             char c = ring.charAt(i);             Set<Integer> set = ringMap.getOrDefault(c, new HashSet<Integer>());             set.add(i);             ringMap.put(c, set);         }         dfs(0, 0, 0);         return ans;     }      public void dfs(int keyIdx, int nowIdx, int stepCounter) {         if (keyIdx == kkey.length()) {             ans = Math.min(ans, stepCounter);             return;         }         Character ch = kkey.charAt(keyIdx);         for (Integer nextIdx : ringMap.get(ch)) {             dfs(keyIdx + 1, nextIdx, stepCounter + 1 + distanceCounter(nowIdx,                     nextIdx));         }      }      public int distanceCounter(int nowIdx, int nextIdx) {         int a = Math.abs(nextIdx - nowIdx);         int b = rring.length() - a;         return Math.min(a, b);     } } 

谢谢

大佬有話說 (0)