Introduction to Computer Science and Programming Using Python - Week 1 - Problem 3

很突然我就決定要開始學Python，這是MITx: 6.00.1x Introduction to Computer Science and Programming Using Python內 Week 1的作業之一 Problem 3。

這裡我想記錄的是我的思緒與解題過程。

題目：取出某一字串內，依字母順序最長的子字串。如：原字串 =  aabcdeaaa，依字母排序最長子字串將會是：aabcde

思緒過程

看到題目時，心中有一些模糊的概念，大概知道要用迴圈。

第一天琢磨了2個多小時，就是沒有門路。後來索性放著，隔天再寫。

第二天仔細推敲一番，覺得解題的關鍵應該在，在腦中或紙上先寫出最終的答案是什麼與找到答案的必要條件是什麼？

在這裡，答案就是依照字母排序的子字串，必要條件就是如何獲得特定的子字串。而要獲得特定的子字串，必須先得知子字串的在原字串的哪個位置，並且在原字串的哪個位子結束。

後來一想，若知道了想要取得的特定子字串的長度，就同時知道這兩個答案。

所以問題變成，如何知道子字串多長？在這個問題上，子字串有多長取決於前一個字母的排序是不是比後一個字母的排序要前面，如果是，則長度增加，如果不是，則長度歸零。

所以我需要將原字串中的每個字母，與下一個字母，兩兩相比。但即使是這樣，我仍舊會得到許多不同子字串的長度。 如 abcedacz，便會得到abce與cz兩個長度的子字串。此時我須得在進行比較，取得最大長度，用取得最大長度時的位子去推敲出子字串的起始點，然後反推出子字串。

想到這裡，差不多也就寫完了。