【數據結構與算法】之深入解析“自由之路”的求解思路與算法示例

一、題目要求

電子游戲“輻射4”中，任務 “通向自由” 要求玩家到達名為 “Freedom Trail Ring” 的金屬表盤，并使用表盤拼寫特定關鍵詞才能開門。

給定一個字符串 ring，表示刻在外環上的編碼；給定另一個字符串 key，表示需要拼寫的關鍵詞，您需要算出能夠拼寫關鍵詞中所有字符的最少步數。

最初，ring 的第一個字符與 12:00 方向對齊，您需要順時針或逆時針旋轉 ring 以使 key 的一個字符在 12:00 方向對齊，然后按下中心按鈕，以此逐個拼寫完 key 中的所有字符。

旋轉 ring 拼出 key 字符 key[i] 的階段中：

可以將 ring 順時針或逆時針旋轉 一個位置，計為 1 步，旋轉的最終目的是將字符串 ring 的一個字符與 12:00 方向對齊，并且這個字符必須等于字符 key[i]；

如果字符 key[i] 已經對齊到12:00方向，需要按下中心按鈕進行拼寫，這也將算作 1 步，按完之后，可以開始拼寫 key 的下一個字符（下一階段），直至完成所有拼寫。

示例 1：

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。