Cookie Consent by Free Privacy Policy Generator 📌 514. Freedom Trail


✅ 514. Freedom Trail


💡 Newskategorie: Programmierung
🔗 Quelle: dev.to

514. Freedom Trail

Hard

In the video game Fallout 4, the quest "Road to Freedom" requires players to reach a metal dial called the "Freedom Trail Ring" and use the dial to spell a specific keyword to open the door.

Given a string ring that represents the code engraved on the outer ring and another string key that represents the keyword that needs to be spelled, return the minimum number of steps to spell all the characters in the keyword.

Initially, the first character of the ring is aligned at the "12:00" direction. You should spell all the characters in key one by one by rotating ring clockwise or anticlockwise to make each character of the string key aligned at the "12:00" direction and then by pressing the center button.

At the stage of rotating the ring to spell the key character key[i]:

  1. You can rotate the ring clockwise or anticlockwise by one place, which counts as one step. The final purpose of the rotation is to align one of ring's characters at the "12:00" direction, where this character must equal key[i].
  2. If the character key[i] has been aligned at the "12:00" direction, press the center button to spell, which also counts as one step. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.

Example 1:

ring

  • Input: ring = "godding", key = "gd"
  • Output: 4
  • Explanation:
For the first key character 'g', since it is already in place, we just need 1 step to spell this character.
For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo".
Also, we need 1 more step for spelling.
So the final output is 4.

Example 2:

  • Input: ring = "godding", key = "godding"
  • Output: 13

Constraints:

  • 1 <= ring.length, key.length <= 100.
  • ring and key consist of only lower case English letters.
  • It is guaranteed that key could always be spelled by rotating ring.

Solution:

class Solution {

    /**
     * @param String $ring
     * @param String $key
     * @return Integer
     */
    function findRotateSteps($ring, $key) {
        $len_key = strlen($key);
        $len_ring = strlen($ring);
        $char_positions = array();

        for($index = 0; $index < $len_ring; $index++) {
            $char = $ring[$index];
            $char_positions[$char][] = $index;
        }

        $dp = array_fill(0, $len_key, array_fill(0, $len_ring, INF));

        foreach($char_positions[$key[0]] as $j) {
            $dp[0][$j] = min($j, $len_ring - $j) + 1;
        }

        for($i = 1; $i < $len_key; $i++) {
            foreach($char_positions[$key[$i]] as $j) {
                foreach($char_positions[$key[$i - 1]] as $k) {
                    $dp[$i][$j] = min($dp[$i][$j], $dp[$i - 1][$k] + min(abs($j - $k), $len_ring - abs($j - $k)) + 1);
                }
            }
        }

        $min_steps = INF;

        foreach($char_positions[$key[$len_key - 1]] as $j) {
            $min_steps = min($min_steps, $dp[$len_key - 1][$j]);
        }

        return $min_steps;
    }
}
...

✅ #514. Freedom Trail


📈 54.22 Punkte

✅ 514. Freedom Trail


📈 54.22 Punkte

✅ Ubuntu's MDS Mitigations Now Available for Intel Cherry Trail and Bay Trail CPUs


📈 37.12 Punkte

✅ Internet regulation: Not a matter of freedom of speech, but freedom to conduct business


📈 26.04 Punkte

✅ Freedom Apk – Download NO ROOT Freedom Apk


📈 26.04 Punkte

✅ Software Freedom Day - Celebrate Software Freedom Day


📈 26.04 Punkte

✅ Software Freedom Law Center Launches Trademark War Against Software Freedom Conservancy


📈 26.04 Punkte

✅ Chromebook Spin 514: Acer packt Ryzen 7 3700C in 14-Zoll-Convertible


📈 22.64 Punkte

✅ Dust 514 - PS3-Spiel wird eingestellt, neuer Eve-Shooter für PC angekündigt


📈 22.64 Punkte

✅ CVE-2024-29672 | zly2006 Reden prior 0.2.514 KeyCallbacks.kt DEBUG_RTC_REQUEST_SYNC_DATA path traversal


📈 22.64 Punkte

✅ Acer stellt neues Chromebook Spin 514 auf AMD-Basis vor


📈 22.64 Punkte

✅ Amazon Deal: Acer Chromebook 514 – 35 Prozent sparen


📈 22.64 Punkte

✅ Acer Chromebook Spin 514: Ryzen 3000C und 16 GB RAM beschleunigen Chrome OS


📈 22.64 Punkte

✅ CVE-2022-24672 | Canon imageCLASS MF644Cdw 10.02 CADM Service heap-based overflow (ZDI-22-514)


📈 22.64 Punkte

✅ CES: Chromebook Spin 514: Acer packt Ryzen 7 3700C in 14-Zoll-Convertible


📈 22.64 Punkte

✅ Acer Chromebook Vero 514 soll mit Nachhaltigkeit punkten


📈 22.64 Punkte

✅ Spin 514: Acer bringt Chromebook-Convertible mit Ryzen 3000C und Radeon-Grafik


📈 22.64 Punkte

✅ Acer Chromebook 514 CB514-1WT im Test: Leises Office-Notebook mit guten Laufzeiten


📈 22.64 Punkte

✅ Test Acer Chromebook 514 CB514: Alu-Chromebook mit Type-C


📈 22.64 Punkte

✅ Shopify Awards $116,000 to Hackers in Canada: h1-514 Recap


📈 22.64 Punkte

✅ Security In 5: Episode 514 - Avoide Those Free USB Charging Hubs


📈 22.64 Punkte

✅ Acer stellt die Chromebooks 314, 317, 514 Spin 713 (2021) vor


📈 22.64 Punkte

✅ Acer Chromebook 514 im Test: Matter Touchscreen unter 500 Euro


📈 22.64 Punkte

✅ Shopify Awards $116,000 to Hackers in Canada: h1-514 Recap


📈 22.64 Punkte

✅ Acer Chromebook 514 im Test: Matter Touchscreen unter 500 Euro


📈 22.64 Punkte

✅ CVE-2024-37393 | SecurEnvoy MFA prior 9.4.514 Desktop Service /secserver ldap injection


📈 22.64 Punkte

✅ Acer präsentiert das Chromebook Spin 514


📈 22.64 Punkte

✅ Acer Chromebook 514: Mit mattem Touchscreen, ab 500 Euro


📈 22.64 Punkte

✅ CVE-2024-4358 | Progress Telerik Report Server 10.0.24.130/10.0.24.514 on IIS authentication spoofing


📈 22.64 Punkte

✅ Acer präsentiert erstes Chromebook mit AMD Ryzen Prozessoren und AMD Radeon Grafik: Chromebook Spin 514


📈 22.64 Punkte

✅ Dust 514 - PS3-Spiel wird eingestellt, neuer Eve-Shooter für PC angekündigt


📈 22.64 Punkte

✅ Meticulous Market Research Pvt. Ltd.: Public Safety and Security Market to Reach $ 514.1 ...


📈 22.64 Punkte











matomo

Datei nicht gefunden!