“This is the 19th day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch card 79 days 🎈!
🚀 Algorithm 🚀

🌲 : Keyboard line

You are given a string array of words that returns only words that can be printed using letters on the same line on an American keyboard. The keyboard is shown below.

In American keyboards:

  • The first line consists of the character “qWERtyuiop”.
  • The second line consists of the character “asDFghjkl”.
  • The third line consists of the character “ZXCVBNM”.

Example 1:

Enter: words = ["Hello"."Alaska"."Dad"."Peace"] output: ["Alaska"."Dad"]
Copy the code

Example 2:

Enter: words = ["omk"] output: []Copy the code

Example 3:

Enter: words = ["adsdf"."sfd"] output: ["adsdf"."sfd"]
Copy the code

Tip:

  • 1 <= words.length <= 20
  • 1 <= words[i].length <= 100
  • Words [I] consists of lowercase and uppercase letters

🌻C# method: sort traversal

We mark each letter with its corresponding line number on the keyboard, and then check that all characters in the string have the same line number.

  • We can pre-compute the line number for each character.

  • When iterating strings, uppercase letters are converted to lowercase letters for easy calculation.

Code:

public class Solution {
    public string[] FindWords(string[] words) {
        IList<string> list = new List<string> ();string rowIdx = "12210111011122000010020202";
        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];
        }
        returnans; }}Copy the code

The execution result

By execution time:152Ms, in all CBeat 49.50% of users in # submissionsMemory consumption:41.4MB, in all C# beat 24.90% of users in submission
Copy the code

🌻Java methods: count

We mark each letter with the corresponding line number on the keyboard, and then check that all characters in the string have the same line number.

  • We can pre-compute the line number for each character.

  • When iterating strings, uppercase letters are converted to lowercase letters for easy calculation.

Code:

class Solution {    
    public String[] findWords(String[] words) {
        List<String> list = new ArrayList<String>();
        String rowIdx = "12210111011122000010020202";
        for (String word : words) {
            boolean isValid = true;
            char idx = rowIdx.charAt(Character.toLowerCase(word.charAt(0)) - 'a');
            for (int i = 1; i < word.length(); ++i) {
                if (rowIdx.charAt(Character.toLowerCase(word.charAt(i)) - 'a') != idx) {
                    isValid = false;
                    break; }}if (isValid) {
                list.add(word);
            }
        }
        String[] ans = new String[list.size()];
        for (int i = 0; i < list.size(); ++i) {
            ans[i] = list.get(i);
        }
        returnans; }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.76% user memory consumption:36.4MB, beat out all Java commits89.40% of the userCopy the code

💬 summary

  • Today is the seventy-ninth day of the buckle algorithm.
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!