Make writing a habit together! This is the fifth day of my participation in the “Gold Digging Day New Plan ยท April More text Challenge”. Click here for more details.

๐Ÿ“ข 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 101st day of continuous clocking of force button algorithm ๐ŸŽˆ!
๐Ÿš€ Algorithm ๐Ÿš€

๐ŸŒฒ A unique email address

Each valid E-mail address consists of a local name and a domain name, separated by the ‘@’ sign. In addition to lowercase letters, E-mail addresses can contain one or more ‘.’ or ‘+’.

For example, in [email protected], Alice is the local name and leetcode.com is the domain name. If you add a period (‘.’) between some characters in the local name part of an E-mail address, messages sent there will be forwarded to the same address without a dot in the local name. Please note that this rule does not apply to domain names.

For example, “[email protected] “and” [email protected] “are forwarded to the same E-mail address. If you add a plus sign (‘+’) to the local name, everything after the first plus sign is ignored. This allows filtering of certain E-mail messages. Again, this rule does not apply to domain names.

For example, [email protected] will be forwarded to [email protected]. You can use both rules together.

If we give you an array of emails with strings, we will send an email to each email [I]. Returns the actual number of different addresses where messages are received.

Example 1:

Enter: emails = ["[email protected]"."[email protected]"."[email protected]"] output:2Explanation: The actual recipient is"[email protected]" ๅ’Œ "[email protected]".Copy the code

Example 2:

Enter: emails = ["[email protected]"."[email protected]"."[email protected]"] output:3
Copy the code

Tip:

  • 1 <= emails.length <= 100
  • 1 <= emails[i].length <= 100
  • The emails[I] are sent by lowercase letters, ‘+’, ‘.’, and ‘@’
  • Each email [I] contains one and only one ‘@’ character
  • All local and domain names are not empty
  • Local names do not begin with a ‘+’ character

๐ŸŒปC# method: normalized representation

Code:

public class Solution {
    public int NumUniqueEmails(string[] emails) {
        HashSet<string> data = new HashSet<string> (); StringBuilder builder =new StringBuilder();
        for(int i=0; i<emails.Length; i++){ builder.Clear();bool judge = true, plus = true;
            for(int j=0; j<emails[i].Length; j++){bool add = true;
                if(judge){
                    if(emails[i][j]=='+')
                    {
                        plus = false;
                    }
                    if(emails[i][j]==The '@')
                    {
                        judge = false;
                        plus = true;
                    }
                    if(emails[i][j]=='. ') {add = false; }}if(add&&plus){
                    builder.Append(emails[i][j]);
                }
            }
            data.Add(builder.ToString());
        }
        returndata.Count; }}Copy the code

The execution result

By execution time:100Ms, in all CBeat 60.14% of users in # submissionsMemory consumption:40.9MB, in all CDefeated 95.70% of users in # submission
Copy the code

๐ŸŒปJava method: Normalized representation

For each E-mail address, we find its normalized representation (that is, an E-mail address with only lowercase letters in its local name after processing the rules for ‘.’ and ‘+’). We perform the following operations for each address in turn:

  • Put email addresses according toThe '@'It is divided into two parts: local name local and domain name reset. The domain name part contains ‘@’ and no additional processing is required.
  • If there is one in the local name'+', remove the ‘+’ and all characters that appear after it;
  • Remove all in the local name'. ';
  • The processed local name and domain name are connected to get a normalized representation of the E-mail addresslocal + rest .

Once we have a normalized representation of all E-mail addresses, we can put them into a Set and get the number of different addresses.

Code:

class Solution {
  public int numUniqueEmails(String[] emails) {
    Set<String> seen = new HashSet();
    for (String email : emails) {
      int i = email.indexOf(The '@');
      String local = email.substring(0, i);
      String rest = email.substring(i);
      if (local.contains("+")) {
        local = local.substring(0, local.indexOf('+'));
      }
      // Note: one should escape the specific character '.',
      // since it is treated as a regex expression.
      local = local.replaceAll("\ \."."");
      seen.add(local + rest);
    }

    returnseen.size(); }}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits76.41% user memory consumption:36.4MB, beat out all Java commits23.53% of the userCopy the code

Complexity analysis

Time complexity: O(MC) where MM is the longest length of all E-mail messages and CC is the number of E-mail addresses. Space complexity: O(MC)Copy the code

๐Ÿ’ฌ summary

  • Today is the 108th 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!