LeetCode500. 鍵盤行

給你一個字串陣列 words ，只回傳可以使用在 美式鍵盤 同一行的字母列印出來的單詞，鍵盤如下圖所示，

美式鍵盤 中：

第一行由字符 "qwertyuiop" 組成，
第二行由字符 "asdfghjkl" 組成，
第三行由字符 "zxcvbnm" 組成，

示例 1：

輸入：words = ["Hello","Alaska","Dad","Peace"]
輸出：["Alaska","Dad"]
示例 2：

輸入：words = ["omk"]
輸出：[]
示例 3：

輸入：words = ["adsdf","sfd"]
輸出：["adsdf","sfd"]

提示：

1 <= words.length <= 20
1 <= words[i].length <= 100
words[i] 由英文字母（小寫和大寫字母）組成

來源：力扣（LeetCode）
鏈接：力扣
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

方法一：暴力法

特點：容易想到，容易編碼，效率感人T.T

相關代碼：C#字串去除串內重復字符

public class Solution
{
    public string[] FindWords(string[] words) 
    {
        return HleetCode.N500KeyboardRow.Commit(words);
    }
    public partial class HleetCode
    {
        //500. 鍵盤行題解
        public static class N500KeyboardRow
        {
            public static string[] Commit(string[] words)
            {
                List<string> res = new List<string>();
                string[] keyboardLines = { "qwertyuiop", "asdfghjkl", "zxcvbnm" };
                //遍歷輸入的字串陣列
                foreach (var wd in words)
                {
                    //字符轉為小寫，再去重，目的是減少對比次數
                    string word = StringEliminateDuplicate(wd.ToLower());
                    for (int i = 0; i < keyboardLines.Length; i++)
                    {
                        bool isRes = true;
                        bool isNotRes = false;
                        //遍歷單詞中的字符
                        for (int j=0;j< word.Length;j++)
                        {
                            if (!keyboardLines[i].Contains(word[j]))
                            {
                                isRes = false;
                                if(j>0) isNotRes=true;//遍歷到第2個以上的字符發現不滿足條件，可以確定不是想要的結果
                                break;
                            }
                        }
                        if(isNotRes) break;//不是想要的結果，直接換下一個單詞
                        if (isRes) res.Add(wd);                          
                    }
                }
                return res.ToArray();      
            }
                //字串去除重復
            private static string StringEliminateDuplicate(string str)
            {
                var strArray = str.Distinct().ToArray();        //字符去重
                return string.Join(string.Empty, strArray);     //字符成串
            }
        }
    }
}

官方暴力版：

特點：

• 將a~z重新編碼為對應的行，減少一層回圈（不過貌似效率差不多T.T）

public class Solution
{
    public string[] FindWords(string[] words) 
    {
        return HleetCode.N500KeyboardRow.Commit(words);
    }

    public partial class HleetCode
    {
        //500. 鍵盤行題解
        public static class N500KeyboardRow
        {
            public static string[] Commit(string[] words)
            {
               
                IList<string> list = new List<string>();
                string rowIdx = "12210111011122000010020202";//將a~z重新編碼為對應的行
                foreach (string word in words) 
                {
                    bool isValid = true;
                    char idx = rowIdx[char.ToLower(word[0]) - 'a'];//存入第一個字符
                    for (int i = 1; i < word.Length; ++i) 
                    {
                        if (rowIdx[char.ToLower(word[i]) - 'a'] != idx) 
                        {
                            isValid = false;
                            break;
                        }
                    }

                    if (isValid) 
                    {
                        list.Add(word);
                    }
                }
           
                string[] ans = new string[list.Count];
                for (int i = 0; i < list.Count; ++i) 
                {
                    ans[i] = list[i];
                }
                return ans;
            }
        }
     
    }
}

方法二：鍵值對

特點：記憶體消耗少

public class Solution 
{

    public string[] FindWords(string[] words)
    {   
        return HleetCode.N500KeyboardRow.Commit(words);
    }

    public partial class HleetCode
    {
        public static class N500KeyboardRow
        {          
            public static string[] Commit(string[] words)
            {
                Dictionary<char,char>  dict= new Dictionary<char,char>();
                foreach(var i in "qwertyuiopQWERTYUIOP") dict.Add(i,'1');   
                foreach(var i in "asdfghjklASDFGHJKL") dict.Add(i,'2');
                foreach(var i in "zxcvbnmZXCVBNM") dict.Add(i,'3');
        
                var list=new List<string>();
                foreach(var word in words)
                {
                    int lineNumber = dict[word[0]];           
                    var match=true;
                    foreach(var c in word)
                    { 
                        if(dict[c]!=lineNumber) 
                        {
                            match=false;
                            break;
                        }
                    }
                
                    if(match) list.Add( word); 
                }
                return list.ToArray();
            }
        }
    }
}