Leetcode 680. Valid Palindrome II

문제 : 680. Valid Palindrome II

등급 : Easy

pub(crate) mod first_try {
    pub struct Solution;
    impl Solution {
        pub fn valid_palindrome(s: String) -> bool {
            Solution::step(&s.chars().collect(), 0, s.len() as isize-1, false)
        }

        fn step(s: &Vec<char>, mut left: isize, mut right: isize, changed: bool) -> bool {
            while left <= right {
                if s[left as usize] == s[right as usize] {
                    left += 1;
                    right -= 1;
                }
                else {
                    if changed {
                        return false
                    }
                    
                    if Solution::step(s, left + 1, right, true) {
                        return true
                    }

                    if Solution::step(s, left, right - 1, true) {
                        return true
                    }

                    return false
                }
            }
        
            true
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::valid_palindrome_ii::first_try::Solution;

    #[test]
    fn example() {
        assert_eq!(Solution::valid_palindrome("aba".to_owned()), true);
        assert_eq!(Solution::valid_palindrome("abca".to_owned()), true);
        assert_eq!(Solution::valid_palindrome("abc".to_owned()), false);
        assert_eq!(Solution::valid_palindrome("a".to_owned()), true);
        assert_eq!(Solution::valid_palindrome("ab".to_owned()), true);
        assert_eq!(Solution::valid_palindrome("dpkytbbmgtastjpwholznqnamjdagzvqsuskivafkjtcyecvmyhofidslrkmizljhzqycmshuovxjixyjtztaljnynbshqdxjhrkrmcevwpepjenbmocvueygrplooemmjdqhmifudnutxpocgsbesemrtrtxlibqqzygenicsadpgmourggfnnrzudjfceljixvnbnqwkjhvfrxdlnbwcshpliuypxfzbwoopfyirsynjsmcoulmkpughluxgjjtchtooudnmrmzjrfrzhnszzuhinsphuwjejaepmdgsjhudtymwlmqoriqqoczcgkndgrsxwjtwvrnwmwaxwukdgayfuybljouojscglrmfpewekpjclozehmfywxnyzadcffltjbhikpfrjcindvomdslyrawtrbkoabpabsvdlktnzgbfgzbhkyuueijvmsjcfgalwkyjebkwxafwcekkwlqfwmecolnqelfabtzrqkkoattgxaxqogaeksqitxhjkgisayepqgqokzwcyyqnzjinzurwvvmsiracaiflcnqioktzvazdjgdpnlayfmvcvbijcrpttygzjdeqlxsdwjqygygefzlyecuoynzkvmfggcerpqxhhueznhzxzuhmbwelezrfzsuwwvjavvldguxazvkrkzajxhltanvhmsnuczhdfswqepkrbxohjhqwxwrbzrrlwpoerpkzczonatpqglqrsobbcqvaanghvuyapznzhflomdbbpdlkbkjhycirxikftehawsftaesoqbuedneglyzawgyrrlykitfeqzmrylfpjarsufokpfowixphvgaduemsemgxjdwkgqwimiuiepzebcfetgpwqtuwhptlnxjwpabtafrgnivojrezicthwfwcltzfrmilhvhuujxtwxbzuoexzvtwipccrdbykatepugzuxloebwzspetoqflcfvgfhhbaxoigopkwmcfdhfksoestwzkmveqwzxlauuxrepqrjeztgiantksmloypgxdynliqthgtfksftcsndyzmtaqaagtjdtjcegffakjsujgzmiyvczqbnyiksbuamuntxetgmjqajsdoxmyivuykijpdxevmbunoqchejtxxiunqcyamcjhblisyckggfxakffnxikazgzdmvcpgliktuslxenhyhyqosxbjzobrsxtwklvuywmgwkfwpnxfdeatipoharmogfizcqlumffjjwgqqqhvibxjkrjlzxvmfxmcdsfqmyviuswxmqtvndrttuadiotrtpptkawgrdigtexcjpyixctibappxffclunaveuitnexngqkvnqfmpsdycpqlwgruznrbfsijzsklxvycxtxfzpjzayjjesreolvhizimhlhtmdvynifpyywkbklmgbqgprfffswmeareakxfbglwudnqfwgrezcjbwnhmlkcbjqbbvxwjowgyvclabogvnwxkfelqimxfauezpmanetjtitmuyfczurksrvfrlwvpyprehjlidhduavsfgoyvsoflklxaoyfhmqjlkerjqnlezabzsnezzpqhcbupnjbzfayzuugnffafnaforgkjupeszxmmngbyneyjgbtfjmlbqqbjbjztbxpdkrubmokivpwhvkbnqpwqisvbrfvhgpowpfnlhtrrdnbrxierpjxdffrlmgybsrtayabopxbolfqabthpcfbhcqjfmqucbvvulmwpssqrhfdhzgenqysoazedsmuddswxuxrxddqazqhoksnclgjarzqjwkeaxghloqtevxiyxvwltmaurqswtxfnrghcwhfxycgfepymjgwgflrinmbzomukfqbfojsahmsubycwblpbwnlrlbfnbipjwhandqpppqixfugsjqhohfwbfdvevkvakwczayzijcavouwcjeemuthhaosubhaajcttzitbsciqulbpuxsorrfwrsvyrdbyhtmcnvnwptkdetvhouxmhgnvohdbmobhmvnilrmfcolpqjsdkqfwcbfzluavombklgkymiymjrpxeudslrsrqpdcazuklplqynuwiwdakuflfrfssvmwqbfirfrjjzxjnptxieqzaprttrxqlbvdoykduhvavjafdewuuitsrabzredmjizzqoseujatlyliietroubkbptgvwrrucbnskxfyhkgbfrpwlfpqhjulyqtfyirxasnqphiasdczognqivucbnotdtkxorkhsjzpkreptimxhmwwdyqyyjrhmwamkwjhfibiyvwfgifafpgfaxwzvnreorkztpovlaeqildsslquziphrozbfslsgkvwcvhocowejwzllriwhruoepexzsiszdzocazctiflhajtqkpymzwhmznsgwleyrkmwvahbqwbqblpqitjwyvcxczluwnibxyjywvubaxkrhkffeiftkmjqepotngjpfhhsbduhsiujjyfbmfegsqlhueihhrildgorbcezugbhknozaucuradcodpalrqnnzyeevsuzxqavdslmwwvgfqhbpzsepelbgilqkgpruxkpicmtaznaahqgquefgavzthtefnpqyofpvlfouxnnbxziplfkwyinxytbrebqqezttzmqsippgehntfapckxkygzfikrqhrueancitrnkhiqneexadkszpothwpczjzanzcgnlocrkeohwoyftnvnthrsukwsqokkuvgfkearyzrycsoiopvkhmxoouhvmawyankhebvbgaqewcrbsdswmuidxvjxfmmjweolmmuqfciosxwffxxmnyjppszlbcoieqqnqmydftdqokyxeelleqrzsqdzpihgrbljpmsnelkulibxkdllxhmkuzebctedztotoijvksmjuyiwsaltljjdjgijkhcxewybrcespgxfgqbvgzcckrazsgxslkopibidwfryazbrvawkbydclkshvnitslxjsuzhmxtfksysgzoihjzeqophgpptvpciszdjwcabrsyioyypflkhzrhcnzvknozsokarutggxekagihrtfgdlsdphpvnojxaoeavjdbukrspkhuqibbyjonhbypbqmtvrrexasvjhkwzgmuqirwutngdyumemtnafthooydcscwasdlqulmwoebuaehhmoezyqrpjgmorntgpjraclaxdgosuvvldnthgvzketsgyvnigpbcsfbgqufmonsbzynrydsnehjxdwfzejbmmhqmdljacemjddynhybfyepivfsffyhaohtubablbyritnxwqhzswnctbxlasbqhobphgrbogozavirmimvessngdarcsccgpthwjuguwsbchiegidujjitgcdmlqtkbuxqgslynacddhqochvoyquepdmgbyuddhilxrorlogeuzaziiluakhejoukcyhqbsbijywqmqhcjhrmniifjvytnztftvgfvbhsvgyylyidyrsmfrrqqembdkemipczmrxnrbitnaogobsrftpbzzasqgvyhairvtynnjbwxooczmtcchbgooqmvkqhuuwnocblkuwxysjpyljuddxvxrcbespyrpatbiubleeecwfgadmfqbnwvejswyhxupietwgxygzdduqswwgfkqjbfqftuorbadqryprdrfnxfrhnnmomlyoyuohwzmnuaeejqxczdgnzbpwtnqxdzrtceisjzmxapdybqdzmuabxxfcmwahxgdbyaxgtzikygsyyqfgzndqlkngunpvgvfyopynrqceghryplajqsbcwfadzuvwdfxymgkvwdbcsbomlcgicfodnivxnadtcprlvlilqsaynmkqkehffkdctxpmgdpamdyqquuiocczruskdirsjpahdqsguegjihdvqbbdihzinskwkjvmxmbaxovdyvhezhdefvgzdtnmgifpujbbmplgpxzanrlwpvkxyjafyiwlmxacbybqmxyslcdzhooczqmuhxhfkoqxggrwkxnpehespkqejkzrdmmsvcxjmuetwvgowgkgfoobpnsxsfhtxgpdchrdkcytpfoycbgjlekrubqrtbtseiqbqzaowslxnnvbxedjxvkttrbcrfhsuidzttkbyanaybzhaacujtcmaxazvmhunashzhfzptjfshiyatotsurgxjdcwkbdgvxqyiisjwtqxzkalrtxykbxhibyrcrlaxgtwplyuykiismmucvdtvwasulsmhejowugbjivtemjurgzejhcdekzyopbcgqjquwvquhctwlqchckjwgkhomimkymvtuxaauzddrybkzvmroxdoxgtrrrvfjewtkbagtnhpubrhwyyvnjumpdfimhabdzxltrtpnetrhhaspegupwwjwbbnqiasdqhthvkkfhfdcginuaqmtuuvhzpreqxocwcnudenscberpqbjevbobovnexpqcbirhaiuyiwzmhtdfjpranbrnydnxdqhunjywygraoeteninldtxdfhuulmnjpflwtqxfpiizmdfmztvhgyppmlkyphaskbcgbfwruskexkitsrgdidjumojuyiaxedlbkrklvbzfqammgklbrapqnveikifxdotmhxppfripnejgmdveemytshugyqubjnngtdntxfmqoynsdqabdwgldjmtwyaxwllcomsnoqhqxgaihtvglnhnalplfeqaazgptriydcqesfxbdexhzxuylxldurvhqzdopzuikvqxmbevqvbszjazndverqzmvyfvrbykugtexgzrjropsorgdncghblblnzcqustnwcrhhayizuhccmwzvwdctkygjggbndhwcpjzsruvuamjhghuckusjrzzrtchvclgzputiunhrxozvzrxxwvnnektlxvsjqdosrvrtspcxuxplavllburrakzpywrdowrwjthbzzbhtjwrwodrwypzkarrubllvalpxuxcpstrvrsodqjsvxltkennvwxxrzvzoxrhnuitupzglcvhctrzzrjsukcuhghjmauvurszjpcwhdnbggjgyktcdwvzwmcchuziyahhrcwntsuqcznlblbhgcndgrosporjrzgxetgukybrvfyvmzqrevdnzajzsbvqvebmxqvkiuzpodzqhvrudlxlyuxzhxedbxfseqcdyirtpgzaaqeflplanhnlgvthiagxqhqonsmocllwxaywtmjdlgwdbaqdsnyoqmfxtndtgnnjbuqyguhstymeevdmgjenpirfppxhmtodxfikievnqparblkgmmaqfzbvlkrkbldexaiyujomujdidgrstikxeksurwfbgcbksahpyklmppyghvtzmfdmziipfxqtwlfpjnmluuhfdxtdlnineteoargywyjnuhqdxndynrbnarpjfdthmzwiyuiahribcqpxenvobobvejbqprebcsneduncwcoxqerpzhvuutmqaunigcdfhfkkvhthqdsaiqnbbwjwwpugepsahhrtenptrtlxzdbahmifdpmujnvyywhrbuphntgabktwejfvrrrtgxodxormvzkbyrddzuaaxutvmykmimohkgwjkchcqlwtchuqvwuqjqgcbpoyzkedchjezgrujmetvijbguwojehmslusawvtdvcummsiikyuylpwtgxalrcrybihxbkyxtrlakzxqtwjsiiyqxvgdbkwcdjxgrustotayihsfjtpzfhzhsanuhmvzaxamctjucaahzbyanaybkttzdiushfrcbrttkvxjdexbvnnxlswoazqbqiesbtrqburkeljgbcyofptyckdrhcdpgxthfsxsnpboofgkgwogvwteumjxcvsmmdrzkjeqkpsehepnxkwrggxqokfhxhumqzcoohzdclsyxmqbybcaxmlwiyfajyxkvpwlrnazxpglpmbbjupfigmntdzgvfedhzehvydvoxabmxmvjkwksnizhidbbqvdhijgeugsqdhapjsridksurzccoiuuqqydmapdgmpxtcdkffhekqkmnyasqlilvlrpctdanxvindofcigclmobscbdwvkgmyxfdwvuzdafwcbsqjalpyrhgecqrnypoyfvgvpnugnklqdnzgfqyysgykiztgxaybdgxhawmcfxxbaumzdqbydpaxmzjsiectrzdxqntwpbzngdzcxqjeeaunmzwhouyoylmomnnhrfxnfrdrpyrqdabroutfqfbjqkfgwwsquddzgyxgwteipuxhywsjevwnbqfmdagfwceeelbuibtaprypsebcrxvxddujlypjsyxwuklbconwuuhqkvmqoogbhcctmzcooxwbjnnytvriahyvgqsazzbptfrsbogoantibrnxrmzcpimekdbmeqqrrfmsrydiylyygvshbvfgvtftzntyvjfiinmrhjchqmqwyjibsbqhyckuojehkauliizazuegolrorxlihdduybgmdpeuqyovhcoqhddcanylsgqxubktqlmdcgtijjudigeihcbswugujwhtpgccscradgnssevmimrivazogobrghpbohqbsalxbtcnwszhqwxntiryblbabuthoahyffsfvipeyfbyhnyddjmecajldmqhmmbjezfwdxjhensdyrnyzbsnomfuqgbfscbpginvygstekzvghtndlvvusogdxalcarjpgtnromgjprqyzeomhheaubeowmluqldsawcscdyoohtfantmemuydgntuwriqumgzwkhjvsaxerrvtmqbpybhnojybbiquhkpsrkubdjvaeoaxjonvphpdsldgftrhigakexggturakoszonkvznchrzhklfpyyoiysrbacwjdzsicpvtppghpoqezjhiozgsyskftxmhzusjxlstinvhsklcdybkwavrbzayrfwdibipoklsxgszarkcczgvbqgfxgpsecrbywexchkjigjdjjltlaswiyujmskvjiototzdetcbezukmhxlldkxbiluklensmpjlbrghipzdqszrqelleexykoqdtfdymqnqqeiocblzsppjynmxxffwxsoicfqummloewjmmfxjvxdiumwsdsbrcweqagbvbehknaywamvhuooxmhkvpoioscyrzyraekfgvukkoqswkusrhtnvntfyowhoekrcolngcznazjzcpwhtopzskdaxeenqihknrticnaeurhqrkifzgykxkcpaftnhegppisqmzttzeqqberbtyxniywkflpizxbnnxuoflvpfoyqpnfethtzvagfeuqgqhaanzatmcipkxurpgkqligblepeszpbhqfgvwwmlsdvaqxzusveeyznnqrlapdocdarucuazonkhbguzecbrogdlirhhieuhlqsgefmbfyjjuishudbshhfpjgntopeqjmktfieffkhrkxabuvwyjyxbinwulzcxcvywjtiqplbqbwqbhavwmkryelwgsnzmhwzmypkqtjahlfitczacozdzsiszxepeourhwirllzwjewocohvcwvkgslsfbzorhpizuqlssdliqealvoptzkroernvzwxafgpfafigfwvyibifhjwkmawmhrjyyqydwwmhxmitperkpzjshkroxktdtonbcuviqngozcdsaihpqnsaxriyftqylujhqpflwprfbgkhyfxksnbcurrwvgtpbkbuorteiilyltajuesoqzzijmderzbarstiuuwedfajvavhudkyodvblqxrttrpazqeixtpnjxzjjrfrifbqwmvssfrflfukadwiwunyqlplkuzacdpqrsrlsduexprjmyimykglkbmovaulzfbcwfqkdsjqplocfmrlinvmhbombdhovnghmxuohvtedktpwnvncmthybdryvsrwfrrosxupbluqicsbtizttcjaahbusoahhtumeejcwuovacjizyazcwkavkvevdfbwfhohqjsgufxiqpppqdnahwjpibnfblrlnwbplbwcybusmhasjofbqfkumozbmnirlfgwgjmypefgcyxfhwchgrnfxtwsqruamtlwvxyixvetqolhgxaekwjqzrajglcnskohqzaqddxrxuxwsddumsdezaosyqnegzhdfhrqsspwmluvvbcuqmfjqchbfcphtbaqflobxpobayatrsbygmlrffdxjpreixrbndrrthlnfpwopghvfrbvsiqwpqnbkvhwpvikomburkdpxbtzjbjbqqblmjftbgjyenybgnmmxzsepujkgrofanfaffnguuzyafzbjnpubchqpzzenszbazelnqjrekljqmhfyoaxlklfosvyogfsvaudhdiljherpypvwlrfvrskruzcfyumtitjtenampzeuafxmiqlefkxwnvgobalcvygwojwxvbbqjbcklmhnwbjczergwfqnduwlgbfxkaeraemwsfffrpgqbgmlkbkwyypfinyvdmthlhmizihvloersejjyazjpzfxtxcyvxlkszjisfbrnzurgwlqpcydspmfqnvkqgnxentiuevanulcffxppabitcxiypjcxetgidrgwaktpptrtoidauttrdnvtqmxwsuivymqfsdcmxfmvxzljrkjxbivhqqqgwjjffmulqczifgomrahopitaedfxnpwfkwgmwyuvlkwtxsrbozjbxsoqyhyhnexlsutkilgpcvmdzgzakixnffkaxfggkcysilbhjcmaycqnuixxtjehcqonubmvexdpjikyuviymxodsjaqjmgtextnumaubskiynbqzcvyimzgjusjkaffgecjtdjtgaaqatmzydnsctfskftghtqilnydxgpyolmsktnaigtzejrqperxuualxzwqevmkzwtseoskfhdfcmwkpogioxabhhfgvfclfqotepszwbeolxuzgupetakybdrccpiwtvzxeouzbxwtxjuuhvhlimrfztlcwfwhtcizerjovingrfatbapwjxnltphwutqwpgtefcbezpeiuimiwqgkwdjxgmesmeudagvhpxiwofpkofusrajpflyrmzqeftikylrrygwazylgendeubqoseatfswahetfkixricyhjkbkldpbbdmolfhznzpayuvhgnaavqcbbosrqlgqptanozczkpreopwlrrzbrwxwqhjhoxbrkpeqwsfdhzcunsmhvnatlhxjazkrkvzaxugdlvvajvwwuszfrzelewbmhuzxzhnzeuhhxqprecggfmvkznyouceylzfegygyqjwdsxlqedjzgyttprcjibvcvmfyalnpdgjdzavztkoiqnclfiacarismvvwruznijznqyycwzkoqgqpeyasigkjhxtiqskeagoqxaxgttaokkqrztbafleqnlocemwfqlwkkecwfaxwkbejykwlagfcjsmvjieuuykhbzgfbgzntkldvsbapbaokbrtwarylsdmovdnicjrfpkihbjtlffcdazynxwyfmhezolcjpkewepfmrlgcsjouojlbyufyagdkuwxawmwnrvwtjwxsrgdnkgczcoqqiroqmlwmytduhjsgdmpeajejwuhpsnihuzzsnhzrfrjzmrmnduoothctjjgxulhgupkmluocmsjnysriyfpoowbzfxpyuilphscwbnldxrfvhjkwqnbnvxijlecfjduzrnnfggruomgpdascinegyzqqbilxtrtrmesebsgcopxtundufimhqdjmmeoolprgyeuvcombnejpepwvecmrkrhjxdqhsbnynjlatztjyxijxvouhsmcyqzhjlzimkrlsdifohymvceyctjkfaviksusqvzgadjmanqnzlohwpjtsatgmbbtykpd".to_owned()), true);
    }
}